题目描述

给定一个整数 $k$，以及白板上写着的 $n$ 个正整数 $a_1,a_2,\dots,a_n$，其中 $1\le a_i\le n$。你可以对白板上的数执行两种操作：

• 擦除（Erase）：选择白板上的任意一个整数并将其擦去。此操作最多可执行 $k$ 次。
• 拆分（Split）：选择白板上任意一个整数 $x\ge 3$，将其拆成三个正整数 $x_1,x_2,x_3$ 满足$$x_1+x_2+x_3=x\quad\text{且}\quad 1\le x_1\le x_2\le x_3. $$

然后将原来的 $x$ 擦去，写入 $x_1$ 和 $x_3$（注意 $x_2$ 被丢弃，不写回白板）。拆分操作可以任意次执行（不限次数）。

对于一组整数集合 $b$，其 美丽值（beauty） 定义为集合中所有元素的最大公约数（GCD），即能整除集合中每个元素的最大整数。

你的任务是：在最多执行 $k$ 次擦除操作并任意次拆分操作后，白板上剩余整数集合的最大可能美丽值是多少？

输入格式

输入包含若干个测试用例。

• 第 $1$ 行：整数 $t$，表示测试用例个数。 ($1\le t\le 10^4$)

• 随后的每个测试用例包含 两行：

• • 第 $1$ 行：两个整数 $n$ 和 $k$ （$1\le n\le 2\cdot10^5$，$0\le k\le n-1$），表示白板上初始整数的个数与最多可执行的擦除次数。
• • 第 $2$ 行：包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le n$），表示白板上初始写的整数。

所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出格式

对于每个测试用例输出一行，包含一个整数——在最多执行 $k$ 次擦除和任意次拆分后，白板上剩余整数的最大可能美丽值（即剩余数的最大公约数的最大值）。

样例输入

6
9 1
4 9 6 8 2 6 7 8 2
10 1
4 9 6 8 2 6 7 8 2 7
7 5
1 1 2 3 4 5 5
7 4
1 1 2 3 4 5 5
14 3
14 12 7 12 9 9 12 4 3 1 3 6 9 13
1 0
1

样例输出

2
1
5
1
3
1

说明

样例 $1$ 解释

初始白板：$[4,9,6,8,2,6,7,8,2]$，允许擦除 $k=1$ 个数。

一种可行操作序列（仅作示例，不必唯一）：

1. 擦除 $7$，白板变为 $[4,9,6,8,2,6,8,2]$。
2. 拆分 $9$ 为 $(2,3,4)$，写回 $2$ 和 $4$（中间的 $3$ 被丢弃）：白板变为$[4,2,4,6,8,2,6,8,2]$。

此时白板上所有数均被 $2$ 整除，故美丽值至少为 $2$，且可以证明无法通过允许的操作得到更大的公约数，故输出为 $2$。