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
hide comments
maverick:
2012-02-09 07:58:24
I am continuously getting
|
|
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)
|
|
যোবায়ের:
2010-12-17 11:12:39
for 6, its 6 itself, counting 1
|
|
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
|
|
.::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 |