問題文

最初、黒板に $1$ つの正整数 $N$ が書かれています。
黒板に正整数 $x$ が書かれているとき、あなたは $x$ の正の約数の個数を $d(x)$ として、黒板の整数を $x-d(x)$ に書き換えるという操作を行います。

例えば、黒板に $6$ が書かれているとき、 $6$ の正の約数の個数は $4$ なので、黒板の数を $2$ に書き換えます。

黒板に書かれた整数が $0$ になるまで操作を繰り返し、 $0$ になったら操作を終了します。(操作を繰り返すと必ず黒板の整数が $0$ になることが証明できます。)
$0$ になる直前に黒板に書かれている正整数を求めてください。

$T$ 個のテストケースについて答えてください。

入力

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

$N$

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^9$
• 入力は全て整数である。

出力

$0$ になる直前に黒板に書かれる整数を出力してください。
$i$ 番目のテストケースに対する答えを $i$ 行目に出力してください。

サンプル

3
6
1
3

2
1
1