设最终选择的区间为 [l,r]。将区间内元素乘上 k 后,整个数组的 gcd 为
记 H=gcd(a1,…,al−1,ar+1,…,an)、I=gcd(al,…,ar)、g=gcd(a1,…,an),显然有 gcd(H,I)=g。
将 H=g⋅h′、I=g⋅i′,且 gcd(h′,i′)=1。则
小苯有一个长度为 n 的数组 {a1,a2,...,an} ,他最多可以执行一次以下操作:
他想知道,操作结束后,数组的 gcd 最大可以变为多少,请你帮他算一算吧。
gcd,即最大公约数。例如,12 和 30 的公约数有 1,2,3,6 其中最大的约数是 6 ,因此 gcd(12,30)=6 。
每个测试文件包含多组测试数据。第一行输入一个整数 T(1≦T≦100) 代表数据组数,每组测试数据描述如下
第一行输入两个正整数
n,k(1≦n≦2×105;1≦k≦109) 代表数组中的元素个数、乘数。
第二行输入 n 个整数 a1,a2,...,an(0≦ai≦109) ,表示数组 a 。
除此之外,保证单个测试文件的 n 之和不超过 3×105 。
对于每一组测试数据,新起一行,输出一个整数,表示操作结束后,数组的 gcd 最大可以变为多少。
输入
2
5 3
1 1 3 6 9
3 1
1 2 3
输出
3
1
说明
对于第一组对试数据,可以选择 [1,2] 这个区间执行操作,执行后数组变为 {3,3,3,6,9} ,此时数组的 gcd 为 3 ,达到最大。
对于第二组测试数据,无论选择哪个区间执行操作,数组的 gcd 都不会改变。