問題文

非負整数 $a, b$ に対し $f(a, b)$ を以下のように定義します。

• $a$ を十進表記した文字列, 小数点 $.$ , $b$ を十進表記した文字列を、この順に結合したものを $s$ とする。 $s$ を十進小数と解釈した有理数を $f(a, b)$ とする。

例えば、 $f(3, 14) = 3.14, ~ f(0, 0) = 0.0, ~ f(17, 888) = 17.888$ です。

非負整数からなる長さ $N$ の数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます。
以下の条件を満たすような正整数 $x$ として、あり得る最小値を求めてください。

• 任意の $1 \leq i \lt j \leq N$ なる整数 $i, j$ に対し、 $\displaystyle f(A_i, A_j) \times x$ は整数である。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力される値はすべて整数
• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$
• 一つの入力における $N$ の総和は $2 \times 10^5$ を超えない

入力

入力は以下の形式で標準入力から与えられます。ここで、 $t$ 番目 $(1 \leq t \leq T)$ のテストケースを $\mathrm{case}_t$ と表します。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられます。

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

$T$ 行出力し、 $t$ 行目には $t$ 番目のテストケースについての答えを出力してください。

サンプル

4
3
3 14 1
2
998244353 0
4
125 5 75 1
10
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

50
1
20
10