Square-Free Numbers

Interview

Time limit2sMemory limit1024 MB

Summary

Given N, find the fewest square-free factors (each greater than 1) whose product is N.

Level: Easy3 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

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, has no 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 contain an integer $N$ .

Output

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

Constraints

$T \le 10^4$
$2 \le N \le 10^6$

Hint

6 can be factored as just 6, since it can only be split further as 2x3, and both parts are square-free. So 6 is a single factor. 8 has to be factored as 2x2x2 so that all factors are square-free.

Examples1

Example 1
Input
```
2
6
8
```
Expected output
```
1
3
```