You are given an array \(a\) of \(n\) integers and another integer \(x\). You need to determine the number of special subsets of those \(n\) integers. If a subset is not empty and the resultant score of that subset is equal to \(x\), then that subset is called a special subset.

Consider a number \(s\) that is equal to the product of all the integers in a subset. The resultant score of that subset is the product of all the distinct prime numbers that divide the number \(s\).

For example, let us consider that \(a = [5, 9, 16, 20, 25]\) and \(x = 10\). Consider the subset \([5, 16, 20]\). The product of all the integers in this subset is \(s = 1600\). The prime numbers that divide this number \(s\) are \(2\) and \(5\). So the resultant score of this subset is \(2*5 = 10\). As this score is equal to \(x\) ,therefore, the selected subset is considered as a special subset.

Input format

First line: A single integer \(t\) that denotes the number of test cases
For each test case:
- First line: Two integers \(n\) and \(x\)
- Next line: \(n\) space-separated integers of the array \(a\)

Output format

For each test case, print a single integer representing the number of special subsets of the given array. Since the answer can be very large, print it modulo \(10^9+7\).

Input Constraints

\(1 \le t \le 5\)
\(1 \le n \le 50000\)
\(1 \le a_i \le 10^6\)
\(2 \le x \le 10^6\)