AT_waipc_qual_a Take Mod for All

長さ $ 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 $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

各テストケースについて答えを出力せよ．

### Sample Explanation 1 例えば， $ 1 $ つめのテストケースでは，以下のように操作を行えばよいです． - $ x=5 $ として操作を行う． $ A $ は $ (2,3,0) $ になる． - $ x=3 $ として操作を行う． $ A $ は $ (2,0,0) $ になる． - $ x=2 $ として操作を行う． $ A $ は $ (0,0,0) $ になる． ### Constraints - $ 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 $ 以下 - 入力はすべて整数