G. Timosh and Set
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Assume there is a positive integer $$$x$$$ and an array $$$a$$$ of size $$$n$$$. In one operation, you can choose any element $$$a_i$$$ $$$(1 \le i \le n)$$$ from the array, then set $$$x:=x- x\mod a_i$$$.

Note $$$f(x)$$$ as the minimum number of operations to make $$$x=0$$$. For a given array $$$a$$$ of size $$$n$$$ and a given integer $$$m$$$, calculate $$$\sum_{i=1}^{m}f(i)$$$.

Input data guarantees that for all $$$x=1,2,\ldots,m$$$, $$$x$$$ can always be reduced to $$$0$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ – the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ $$$(2 \le n \le 2 \cdot 10^5 , 1 \le m \le 10^7)$$$ – the length of set $$$a$$$ and integer $$$m$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le 10^7)$$$.

Input data guarantees that for all $$$x=1,2,\ldots,m$$$, $$$x$$$ can always be reduced to $$$0$$$.

It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

It's guaranteed that the sum of $$$m$$$ doesn't exceed $$$10^7$$$.

Output

For each test case, output an integer in a new line  — $$$\sum_{i=1}^{m}f(i)$$$.

Example
Input
2
4 6
1 2 3 4
2 7
2 5
Output
10
12
Note

In the first test case,

  • $$$f(1)=f(2)=f(3)=1$$$;
  • $$$f(4)=f(5)=2$$$;
  • $$$f(6)=3$$$.

So the answer is $$$1+1+1+2+2+3=10$$$.