D. DBSucks-ugly Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Team DBSucks did a terrible performance testing this contest, they were pretty slow. They farmed all possible penalties. Here is a problem with credit to their shameful performance.

You will be given an array $$$A$$$ of $$$N$$$ elements and an integer $$$M$$$, count the number of integers $$$X$$$ $$$(1 \le X \le M)$$$ that are co-prime with all elements of the array.

Note that: two integers are said to be co-prime if their greatest common divisor is $$$1$$$.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains a two integers $$$N$$$ and $$$M$$$ $$$(1 \le N$$$, $$$M \le 10^5)$$$ — the size of the array $$$A$$$ and the number $$$M$$$.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le 10^5)$$$ — the values of the array $$$A$$$.

It's guaranteed that the sum of $$$N$$$ and the sum of $$$M$$$ over all testcases does not exceed $$$10^5$$$

Output

For each testcase print a single integer — the number of integers that are co-prime with all elements of the array.

Example
Input
1
3 5
1 2 3
Output
2