Chung, the self-proclaimed "Grand Alchemist," has returned to challenge the talents of BKCC#3. This time, he has unearthed a row of ancient mana stones, but he lacks the magical prowess to stabilize their volatile energy.

He has arranged ~n~ crystals in a sequence, where the ~i~-th crystal possesses a power level of ~a_i~. A "Fusion" is created by combining the power of a contiguous sequence of crystals. If we select crystals from index ~l~ to ~r~, the total energy ~X~ is the product of their individual powers: $$X = a_l \times a_{l+1} \times \cdots \times a_r$$

However, a Fusion is unstable in its raw form. To stabilize it, the total energy ~X~ must be partitioned into two distinct components, positive values ~A~ and ~B~, such that:

• The product restores the total energy: ~A \times B = X~.

• The components are structurally distinct: ~A < B~.

• The components share no common resonance: ~A~ and ~B~ are coprime (i.e., ~\gcd(A, B) = 1~).

Chung defines the stability function ~f(X)~ as the number of valid ways to partition the energy ~X~ according to these rules.

To prove your mastery over the arcane arts, you must calculate the Grand Resonance S, defined as product of ~f(X)~ for every possible contiguous sub-segment of the crystal sequence modulo ~10^9 + 7~. Formally:

$$S = \prod_{1 \le l \le r \le n}{f(a_l \times a_{l+1} \times \cdots \times a_{r-1} \times a_r)} \mod 10^9 + 7$$

Input

The first line contains a positive integer ~T~ — the number of test cases.

Each test case is described as follows:

• The first line contains a positive integer ~n~ (~n \le 2 \times 10^5~).

• The next line contains ~n~ positive integers ~a_1, a_2, \cdots, a_n~ (~2 \le a_i \le 10^6~).

The data guarantees that the total ~n~ across all test cases does not exceed ~2 \times 10^5~.

Output

For each test case, print an integer — the value of ~S~.

Sample Input 1

3
1
15
3
3 4 5
4
2 2 3 4

Sample Output 1

2
16
32

Notes

In the first test case, ~15~ can only be partitioned as (~1, 15~) and (~3, 5~), so there are ~2~ possible pairs.

In the second test case, consider all segments as follows:

• ~[3] \rightarrow 3 \rightarrow (1,3) \rightarrow~ ~1~ pair

• ~[4] \rightarrow 4 \rightarrow (1,4) \rightarrow~ ~1~ pair

• ~[5] \rightarrow 5 \rightarrow (1,5) \rightarrow~ ~1~ pair

• ~[3,4] \rightarrow 12 \rightarrow (1,12), (3,4) \rightarrow~ ~2~ pairs

• ~[4,5] \rightarrow 20 \rightarrow (1,20), (4,5) \rightarrow~ ~2~ pairs

• ~[3,4,5] \rightarrow 60 \rightarrow (1,60), (4, 15), (3, 20), (5, 12) \rightarrow~ ~4~ pairs

Thus, ~S = 1 \times 1 \times 1 \times 1 \times 2 \times 2 \times 4 = 16~