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 squarefree. A squarefree 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 squarefree factors.
Constraints
T <= 10^{4}
2 <= N <= 10^{6}
Example
SAMPLE INPUT 2 6 8 SAMPLE OUTPUT 1 3
hide comments
karthik1997:
20160609 17:27:11
Nice Que :) AC 0.00s in first Go :D


minhthai:
20160215 15:46:44
very nice problem :) very creative :D 

Shashank Tiwari:
20151212 21:58:53
Question can be restated as :


ASHUTOSH DWIVEDI:
20151029 16:41:35
Last edit: 20151107 20:31:21 

:.Mohib.::
20150803 20:53:20
Great...!! 

Madhav:
20150329 14:08:14
good concept!!


Malinga:
20150109 09:32:09
Sieve+fast I/O...AC in 1.19 sec 

Anubhav Balodhi :
20141230 09:35:03
Mathematical one ^_^ 

BLANKRK:
20140625 22:40:56
nice !!! :) 

abhishek nagpal:
20130901 12:03:17
what will be the answer for 44?

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