AMR10C - Square Free Factorization

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

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

hide comments
2012-02-09 07:58:24 maverick
I am continuously getting
Error

Wrong problem code!

Please fix this error! I think the problem is temporarily removed from the main problemset.
2010-12-27 18:20:16 Kennard
36? is the answer is 2 or 4?
2010-12-24 09:42:26 mohit
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
2010-12-17 09:04:31 Agus Nugroho
what will be the answer for 18?
2010-12-15 01:07:28 Rahul
can someone please say how the output is coming for 6,8 and 24 ?
2010-12-14 11:12:36 Ankul Garg
i did pre-processing and for T = 10^4 and N = 10^6, it takes 78ms on my system, still TLE :-(
2010-12-13 17:14:05 olimpoUS
in
24
out
3
2010-12-13 11:40:11 .::Manish Kumar::.
what will be the ans for 24?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.