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

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