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\)