You are given an integer $k$ and $n$ positive integers $a_1, a_2, \ldots, a_n$ written on a whiteboard, where $1\le a_i\le \boldsymbol{n}$. You may perform the following operations:

• Erase: Choose an integer from the whiteboard and erase it. This operation can be performed at most $k$ times.
• Split: Choose an integer $x\ge 3$ from the whiteboard. Split it into three positive integers $x_1$, $x_2$, and $x_3$ such that $x_1 + x_2 + x_3 = x$, and $1\le x_1\le x_2\le x_3$. Then, erase $x$ from the whiteboard and write two new integers $x_1$ and $x_3$ on the whiteboard. Note that $x_2$ is discarded and not written on the whiteboard. This operation may be performed any number of times.

The beauty of a collection of integers $b$ is defined as the greatest common divisor of all the elements in $b$. Formally, it is the largest integer $d$ such that $d$ divides $x$ for every $x$ that is an element of $b$.

Your task is to determine the maximum possible beauty of the integers on the whiteboard after performing at most $k$ Erase operations and any number of Split operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1\le n \le 2 \cdot 10^5$, $0 \le k \le n - 1$) — the number of integers on the whiteboard, and the maximum number of Erase operations allowed.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le \boldsymbol{n}$) — the integers initially written on the whiteboard.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer representing the maximum beauty of the elements written on the whiteboard after performing the operations.

Note

In the first test case, you may perform the following sequence of operations:

• Erase $7$. The whiteboard now contains the integers $[4,9,6,8,2,6,8,2]$.
• Split $9$ into three integers $2$, $3$, and $4$. $9$ is erased from the whiteboard, and two new integers $2$ and $4$ are written. The whiteboard now contains the integers $[4,\underline{2,4},6,8,2,6,8,2]$.
• Split $8$ into three integers $2$, $2$, and $4$. $8$ is erased from the whiteboard, and two new integers $2$ and $4$ are written. The whiteboard now contains the integers $[4,2,4,6,\underline{2,4},2,6,8,2]$ (It does not matter which $8$ Split is performed on as the ordering in the array does not matter).

The beauty of the integers on the whiteboard after the operations is $2$ as it is the largest number that divides all the integers on the whiteboard ($2$, $4$, $6$, and $8$). Note that the last operation is unnecessary — the beauty of the integers on the whiteboard after the second operation is already $2$.

In the second test case, note that the Erase operation can only remove one occurrence of an integer, even if duplicates exist. Here, we are only able to erase one copy of $7$, so there will still be one remaining $7$ on the whiteboard. Hence, we are unable to perform the same sequence of operations as in the first test case.

In the third test case, we can erase integers $1$, $1$, $2$, $3$, and $4$, leaving only $[5, 5]$ on the whiteboard. Since both numbers are $5$, their greatest common divisor is $5$, and the maximum beauty is $5$.