You are given an array $$A$$ containing $$N$$ positive integers. Consider an array $$B$$ that also contains $$N$$ positive integers and it satisfies the following condition: 

• For all $$i$$, consider $$j$$ such that \(1 \le i < j \le N, A_iB_i = A_jB_j\) holds correct. 

Find the minimum possible value of \(B_1 + B_2 + ...+ B_N\) for array $$B$$. Since the answer can be large, print the sum modulo \(1000000007\).

Input format

• The first line contains an integer $$T$$ denoting the number of test cases.
• The first line of each test case contains a single integer $$N$$ denoting the size of the array $$A$$.
• The second line of each test case contains $$N$$ space-separated integers denoting the array $$A$$.

Output format

For each test case, print the sum modulo $$1000000007$$ in a new line.

Constraints

\(1 \le T \le 10000\\ 1 \le N \le 200000\\ 1 \le A_i \le 1000000\)

The sum of $$N$$ over $$T$$ test cases does not exceed $$200000$$.