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$.