AMR10C - Square Free Factorization

no tags 

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 testcase, output the smallest number of square-free factors.

Constraints

T <= 104
2 <= N <= 106

Example

SAMPLE INPUT
2
6
8

SAMPLE OUTPUT
1
3

hide comments
maverick: 2012-02-09 07:58:24

I am continuously getting
Error

Wrong problem code!

Please fix this error! I think the problem is temporarily removed from the main problemset.

Kennard: 2010-12-27 18:20:16

36? is the answer is 2 or 4?

mohit: 2010-12-24 09:42:26

i am getting runtime error(SIGFPE)
submission no 4486705

যোবায়ের: 2010-12-17 11:12:39

for 6, its 6 itself, counting 1
for 8, its 2, 2, 2, counting 3
for 18, its 3, 6, counting 2
for 24, its 2, 2, 6, counting 3
problem wants you to factor the given number in such a way that each factor is a square free number.

Last edit: 2010-12-17 11:26:32
Agus Nugroho: 2010-12-17 09:04:31

what will be the answer for 18?

Rahul: 2010-12-15 01:07:28

can someone please say how the output is coming for 6,8 and 24 ?

Ankul Garg: 2010-12-14 11:12:36

i did pre-processing and for T = 10^4 and N = 10^6, it takes 78ms on my system, still TLE :-(

olimpoUS: 2010-12-13 17:14:05

in
24
out
3

.::Manish Kumar::.: 2010-12-13 11:40:11

what will be the ans for 24?


Added by:Varun Jalan
Date:2010-12-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem, ICPC Asia regionals, Amritapuri 2010