Unit Power Subsets

You are given an integer array ‘Arr’. You are required to calculate the number of subsets whose product can be represented as the product of unit powers of one or more distinct primes. As the answer can be large calculate it modulo (10^9+7).

Note: Subsets are considered distinct if the chosen set of indexes are different.

For Example:

Suppose arr = [1, 3, 9, 5]

Valid subsets are as follows:
[3], Product = 3.
[1, 3], Product = 1 * 3.
[5], Product = 5.
[1, 5], Product = 1 * 5.
[3, 5], Product = 3 * 5.
[1, 3, 5], Product = 1 * 3 * 5.
All of the above subsets’ products can be represented only with unit powers of prime and have at least one prime in their product. Hence they are valid. As we have six valid subsets, our output will be 6.

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single integer ‘N’, denoting the size of ‘Arr’.

The second line of each test case contains ‘N’ space-separated integers, denoting the elements of ‘Arr’.

Output Format:

For each test case, print a single integer value denoting the number of valid subsets modulo (10^9+7).

Print a separate line for each test case.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 1000
1 ≤ N ≤ 10^5
1 ≤ Arr[i] ≤ 20
1 ≤ ΣN ≤ 2 * 10^5

Time limit: 1 Sec

Sample Input 1 :

2
4
1 3 9 5
3
14 15 2

Sample Output 1 :

6
5

Explanation For Sample Input 1 :

For First Case - Same as explained in above example.

For the second case - 

arr = [14, 15, 2]
[14], Product = 2 * 7.
[15], Product = 3 * 5.
[2], Product = 2.
[14, 15], Product = 2 * 3 * 5 * 7.
[2, 15], Product = 2 * 3 * 5.
All of the above subsets’ products can be represented only with unit powers of prime and have at least one prime in their product. Hence they are valid. As we have five valid subsets, our output will be 6.

Sample Input 2 :

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

Sample Output 2 :

38
56