Ideal Elections

Time Limit	Memory	Input	Output
2 s	64 MB	stdin	stdout

Time Limit

Memory

Input

Output

2 s

64 MB

stdin

stdout

Work one prime at a time, and remember the answer can be enormous - keep it modulo 10^9 + 7.

Elections for the title of "Best Number" are being held in Saransk. There are $n$ people at the polling station, and the $i$ -th of them carries a number $a_{i}$ .

When a person steps into the booth, they do not vote for their own number - they vote for a candidate that is a divisor of it. So the $i$ -th person picks some $p_{i}$ that divides $a_{i}$ (this can be $1$ , or $a_{i}$ itself, or anything in between).

After everyone has voted we are left with an array of votes $[p_{1}, p_{2}, \dots, p_{n}]$ . The organizer calls the vote ideal when the least common multiple of all the votes equals their product:

l c m (p_{1}, p_{2}, \dots, p_{n}) = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}

Here $l c m$ is the least common multiple - the smallest number divisible by every $p_{i}$ .

Count how many different ideal arrays of votes are possible. Two arrays are different if they differ in at least one position. The count can be enormous, so print it modulo $1 0^{9} + 7$ .

Input

The first line contains the number of test cases $t$ .

Each test case takes two lines. The first line has a single integer $n$ - the number of voters. The second line has $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ - the numbers they carry.

The sum of $n$ over all test cases does not exceed $1 0^{5}$ .

Output

For each test case print one line: the number of ideal vote arrays, modulo $1 0^{9} + 7$ .

Example

Input

4
4
2 3 1 4
2
2 4
6
3 9 1 6 4 5
7
1 2 3 67 13 8 8

Output

In the first test we have $8$ valid arrays - for example everyone voting $1$ , or the fourth person voting $4$ while the rest vote $1$ , etc..

Constraints

$1 \leq t \leq 1 0^{4}$
$1 \leq n \leq 1 0^{5}$
$1 \leq a_{i} \leq 5 \cdot 1 0^{5}$
The sum of $n$ over all test cases does not exceed $1 0^{5}$ .

This problem was adapted from Elections in Saransk (easy version), problem F1 of Codeforces Round 1103 (Div. 3).

Time Limit	Memory	Input	Output
2 s	64 MB	stdin	stdout

Elections for the title of "Best Number" are being held in Saransk. There are $n$ people at the polling station, and the $i$ -th of them carries a number $a_{i}$ .

l c m (p_{1}, p_{2}, \dots, p_{n}) = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}

Here $l c m$ is the least common multiple - the smallest number divisible by every $p_{i}$ .

Count how many different ideal arrays of votes are possible. Two arrays are different if they differ in at least one position. The count can be enormous, so print it modulo $1 0^{9} + 7$ .

Input

The first line contains the number of test cases $t$ .

Each test case takes two lines. The first line has a single integer $n$ - the number of voters. The second line has $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ - the numbers they carry.

The sum of $n$ over all test cases does not exceed $1 0^{5}$ .

Output

For each test case print one line: the number of ideal vote arrays, modulo $1 0^{9} + 7$ .

Example

Input

4
4
2 3 1 4
2
2 4
6
3 9 1 6 4 5
7
1 2 3 67 13 8 8

Output

In the first test we have $8$ valid arrays - for example everyone voting $1$ , or the fourth person voting $4$ while the rest vote $1$ , etc..

Constraints

$1 \leq t \leq 1 0^{4}$
$1 \leq n \leq 1 0^{5}$
$1 \leq a_{i} \leq 5 \cdot 1 0^{5}$
The sum of $n$ over all test cases does not exceed $1 0^{5}$ .

This problem was adapted from Elections in Saransk (easy version), problem F1 of Codeforces Round 1103 (Div. 3).

Ideal Elections

Input

Output

Example

Constraints

Submit your solution

Ideal Elections

Input

Output

Example

Constraints

Submit your solution