F. Subsequence GCD
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Sanji is cooking a brand-new recipe in the galley, but he needs the perfect ratio of ingredients. Sherbiny gives him an array $$$a_1, a_2, \ldots, a_n$$$.

Consider all $$$2^n$$$ subsequences of the array, including the empty subsequence.

A subsequence is obtained by choosing some indices of the array and keeping the chosen elements in their original relative order. Different choices of indices are considered different subsequences, even if they produce the same sequence of values.

For a subsequence $$$b_1, b_2, \ldots, b_m$$$, define its flavor score as $$$\sum_{i=2}^{m} \gcd(b_i, b_{i-1}).$$$

We define $$$\gcd(0,0)=0$$$. The empty subsequence and every subsequence of length $$$1$$$ have a flavor score of $$$0$$$.

Sherbiny writes the flavor scores of all $$$2^n$$$ subsequences in non-increasing order. Equal scores are kept as separate entries in this order.

Sanji wants to find the $$$k$$$-th score in this order.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 1000$$$, $$$k \le 2^{n}$$$).

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \dots, a_{n}$$$ ($$$0 \le a_{i} \le 10^{9}$$$).

It is guaranteed that the sum of $$$n * k$$$ over all test cases does not exceed $$$2 \times 10^{6}$$$.

Output

For each test case, output one integer — the $$$k$$$-th biggest score.

Example
Input
2
3 2
4 6 2
4 3
1 2 3 4
Output
2
2
Note

In the first test case, the array is [4,6,2].

  • The subsequence [4, 6, 2] has value $$$gcd(4,6)+gcd(6,2)=2+2=4$$$.
  • Each of the subsequences [4, 6], [4,2], and [6, 2] has value 2.
  • Every other subsequence (including all subsequences of length at most 1, and the empty subsequence) has value 0.

Sorting all 8 values in non-increasing order gives 4, 2, 2, 2, 0, 0, 0, 0, so the 2-nd maximum is 2.