N. Fixing The Servers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Da7doo7 was working for Telekilogram(the bigger Telegram) but he broke the server and got fired.

As the Telekilogram servers are going down, you and your classmates started to panic. Luckily, Telekilogram decided that every connected group of people should register a group account.

What is a group account? It is a way to solve the problem since a group of $$$n$$$ people needs to stay connected. The group account provides them with $$$n-1$$$ connections where in each connection, person $$$x$$$ and person $$$y$$$ can chat together. The purpose of the group account is to keep everyone connected using the least amount of server power.

The $$$i$$$-th student has a value $$$a_i$$$ that explains his interests and personality. Using this number, the compatibility of two students $$$x$$$ and $$$y$$$ is $$$\gcd(a_x, a_y)$$$. For example: if student $$$x$$$ has the value $$$12$$$ and student $$$y$$$ has the value $$$18$$$ then their compatibility is $$$6$$$.

Your class knows that you are the best problem solver, so they asked you to assign the connections in such a way that the sum of compatibilities is maximized. Given that all members in your class have values at most $$$m$$$, please, help them resolve this issue.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 2000)$$$ representing the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1\le n\le 5\cdot 10^5, 1\le m \le 10^6)$$$ — the size of the class and the maximum value possible of all members.

The last line of each test case contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1\le a_i \le m$$$) — the value of each member of the class.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$, as well as the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer denoting the maximum sum of compatibilities that can be achieved.

Example
Input
3
3 10
2 6 8
2 2
1 2
4 4
1 2 3 4
Output
4
1
4