問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます． ここで，2 \leq N および A_1 < A_2 < \cdots < A_N が保証されます．

あなたは今から以下の操作を 1 回以上行います．

• 正整数 x を選ぶ．そして，すべての i (1 \leq i \leq N) について，A_i の値を，A_i を x で割ったあまりで置き換える．

ここで，操作列のスコアを，操作で使用した x の最小値と定義します．

あなたの目標は，A のすべての要素が等しい状態にすることです． 目標を達成する操作列のスコアとしてあり得る最大値を求めてください．

1 つの入力につき，T ケースを解いてください．

制約

• 1 \leq T \leq 125000
• 2 \leq N \leq 250000
• 0 \leq A_1 < A_2 < \cdots < A_N \leq 10^9
• T ケースにわたる N の総和は 250000 以下
• 入力はすべて整数

入力例 1

4
3
2 3 5
4
4 10 15 25
5
0 10 20 30 40
15
52633263 109965057 177443516 242738411 319866698 372592710 429724665 485840965 570195620 653861052 725414602 781977517 835165877 912632268 988630679

出力例 1

2
6
10
57331794

例えば，1 つめのテストケースでは，以下のように操作を行えばよいです．

• x=5 として操作を行う．A は (2,3,0) になる．
• x=3 として操作を行う．A は (2,0,0) になる．
• x=2 として操作を行う．A は (0,0,0) になる．