E. Unwanted Divisors Again
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You're given an array of integers $$$a_1, a_2, \dots, a_n$$$ and an integer $$$m$$$. Find the number of divisors of $$$m$$$ that don't have any multiples in $$$a$$$.

In other words, count the number of integers $$$d$$$ satisfying -

  • $$$d$$$ divides $$$m$$$.
  • $$$d$$$ doesn't divide $$$a_i$$$ for $$$1 \leq i \leq n$$$.
Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$\left(1 \leq n \leq 10^6;\ 1 \leq m \leq 10^9\right)$$$ — the length of the array and the given integer.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the array.

Output

For each test case, output the number of divisors of $$$m$$$ that don't have any multiples in $$$a$$$.

Example
Input
3
3 6
1 3 10
1 1
1
4 12
1 4 6 10
Output
1
0
1