Find the largest prime factor of each queried integer.

Input

The first line contains \(T\). Each of the next \(T\) lines contains \(N\).

The input satisfies:

• \(1 \le T \le 500\)
• \(2 \le N \le 10^7\)

Output

For each query, print the largest prime factor on its own line.

Example

Input

1
2

Output

2