405556: GYM101992 D The Millennium Prize Problems

Did you hear about the Millennium Prize Problems? They are seven problems in mathematics that were stated by the Clay Mathematics Institute on May 24, 2000. A correct solution for any of these problems results in a million dollar prize being awarded by the institute to the discoverer(s).

Soliman, one of the ECPC judges came up with a new mathematics problem and claimed that it should be the eighth Millennium Prize Problem as he is pretty sure no one could solve it. Here's the problem:

Given an array $$$A$$$ of length $$$N$$$ (the array can have duplicate values). What is the sum of all least common multiple (LCM) values for every pair of the array? More formally you need to calculate the following: $$$$$$ \sum_{i=1}^N \sum_{j=1}^N \text{LCM}(A_i, A_j)$$$$$$

Tefa, one of the ECPC judges suggested that we can add it in the problem set to see if someone can come up with a solution, so can you do it?

The first line of the input contains a single integer $$$T$$$ the number of test cases, each test case consists of one line containing $$$N + 1$$$ space-separated integers, the first integer is the number $$$N$$$ the size of the array and the remaining integers are the elements of the array $$$A$$$, where $$$1 \leq N \leq 10^5$$$ and $$$1 \leq A_i \leq 10^5$$$.

For each test case output the answer to the problem modulo $$$10^9+7$$$.

2
4 2 6 12 15
5 2 3 7 11 12

335
861