You all know about factorization of an integer. Here we want you to factor a number into as few factors as possible. That is easy, you say, just have the number itself, and that will be the smallest number of factors i.e. 1.

But wait, I haven't finished — each of the factors that you find must be square-free. A square-free number, however you factor it, won't have any factor that is a perfect square.  Of course, you can never include 1 as a factor.

Input

The first line of input is the number of test cases T. The next T lines each have an integer N.

Output

For each test case, output the smallest number of square-free factors.

Constraints

T ≤ 10⁴
2 ≤ N ≤ 10⁶

Example

Input:
2
6
8

Output:
1
3