Description

小黄得到了一个正整数 $n$，小黄将用这个正整数和任意一个正整数求一次最大公因数。小黄想要知道除了 $1$ 以外，这些最大公因数中最小的一个是多少。

Format

Input

第一行有一个整数 $t\ (1 \leq t \leq 1000)$，表示测试用例数。

每个测试用例有一行，包含一个整数 $n\ (2 \leq n \leq 10^9)$，表示题目中用来和其他正整数求最大公因数的正整数。

Output

每个测试用例输出一行一个整数，表示除了 $1$ 以外，求出的最大公因数中最小的一个是多少。

Samples

2
5
114514

5
2

Limitation

1s, 1024KiB for each test case.