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$