Problem of the day
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.
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’.
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.
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
1 ≤ T ≤ 1000
1 ≤ N ≤ 10^5
1 ≤ Arr[i] ≤ 20
1 ≤ ΣN ≤ 2 * 10^5
Time limit: 1 Sec
2
4
1 3 9 5
3
14 15 2
6
5
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.
2
7
1 2 3 4 5 6 7
8
1 5 2 8 1 7 1 9
38
56