题目背景

编造的故事 又写入谁的梦境

烧掉的诗句 又变成谁的回忆

——MOCKER44.《缥缈愿》

题目描述

“一朝出师　自树其帜　心怀天下　少年壮志”

愿望虚无缥缈。小 K 有 $n$ 个愿望，用一个长为 $n$ 的序列 $a$ 表示，其中 $a_i$ 表示第 $i$ 个愿望的强度。

某日，小 K 想将 $n$ 个愿望综合起来，以此确立自己的志向。具体地，他的志向强度将为所有 $a_i$ 的最大公约数。在确立志向之前，他可以选择一个区间 $[l,r]$，将该区间内愿望的强度增加 $k$，也可以不加强。他想让自己的志向强度尽可能大，请你帮他求出可能的最大强度值。

由于愿望太缥缈了，小 K 不怎么确定 $a_i$ 的值，因此你需要处理 $T$ 组数据。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来依次输入每组数据，每组数据如下：

第一行两个整数 $n,k$，表示愿望的个数和加强参数。

第二行 $n$ 个整数 $a_i$，表示每个愿望的初始强度。

输出格式

输出 $T$ 行，每行一个整数，表示志向的最大强度值。

输入输出样例 #1

输入 #1

2
6 2
5 3 13 8 10 555
3 1
3 6 9

输出 #1

5
3

输入输出样例 #2

输入 #2

3
6 61
209 551 304 323 285 114
6 472
720 320 1373 1653 1413 640
6 595
1140 228 399 1482 342 513

输出 #2

19
5
57

输入输出样例 #3

输入 #3

1
4 2
15 3 13 9

输出 #3

3

说明/提示

本题输入量较大，建议使用较快速的读入方式。保证时间限制不低于 std 运行时间的 $3$ 倍。

对于所有数据，$1\le T \le 3,1\le n\le 6\times 10^5,1\le a_i,k\le 10^{18}$，下表中的 $res$ 表示答案。

\begin{array}{|c|c|c|c|} \hline \textbf{测试点编号 } &n\le & a_i,k\le & \textbf{特殊性质}\\ \hline 1,2 & 100 & 10^9 & \textbf{无}\\ \hline 3,4,5,6 & 2000 & 10^9 & \textbf{无}\\ \hline 7,8,9,10 & 2\times 10^5 & 10^{18} & res\le40\\ \hline 11 & 6\times 10^5 & 10^{18} & a_1=1\\ \hline 12 & 6\times 10^5 & 10^{18} & a_n=1\\ \hline 13,14,15 & 2\times 10^5 & 10^{10} & \textbf{无}\\ \hline 16,17,18 & 4\times 10^5 & 10^{14} & \textbf{无}\\ \hline 19,20 & 6\times 10^5 & 10^{18} & \textbf{无}\\ \hline \end{array}