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
[Rampage] Blue.Mary:
20220817 10:01:14
@nayeem2021: It's possible that your ability of reading and understanding problem statement has some problem. 

nayeem2021:
20220814 08:15:30
The problem statement should be clarified and rewritten again. Very pathetic description. It's programming problem not some riddle by a Riddler. 

Shubham Jadhav:
20200711 10:36:45
Sounds intimidating, but is really easy 

shakib19:
20200623 10:42:47
why i got WA?


zihadboss:
20191016 12:24:39
hi 

towhid1zaman:
20190618 20:55:52
prime factorization + map  AC in 0.19s 

roni_roy18:
20190529 08:11:50
AC in 1st attempt & also 0.00 sec :)


koushiq:
20181121 11:46:47
intimidating one ! 

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 
Added by:  Varun Jalan 
Date:  20101213 
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 