给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$，你需要执行恰好 $k$ 次操作。 每次操作中，你需要选择一个元素并将其值增加 $1$。 请最大化操作后所有元素的最大公约数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试数据组数。对于每组测试数据： 第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^6, 1 \le k \le 10^{12}$)，表示序列的长度和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)，表示该序列。 保证所有测试数据的 $n$ 之和不超过 $10^6$，所有测试数据的 $\max a_i$ 之和不超过 $10^6$，且所有测试数据的 $k$ 之和不超过 $10^{12}$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示在执行恰好 $k$ 次操作后，所有元素可能的最大公约数。

样例

输入 1

2
3 6
2 9 8
3 7
2 9 8

输出 1

5
2

说明

对于第一个样例测试数据，我们可以将序列变为 $5, 10, 10$，此时最大公约数为 $5$。 对于第二个样例测试数据，我们可以将序列变为 $6, 10, 10$，此时最大公约数为 $2$。