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
2022-08-17 10:01:14 [Rampage] Blue.Mary
@nayeem2021: It's possible that your ability of reading and understanding problem statement has some problem.
2022-08-14 08:15:30
The problem statement should be clarified and re-written again. Very pathetic description. It's programming problem not some riddle by a Riddler.
2020-07-11 10:36:45 Shubham Jadhav
Sounds intimidating, but is really easy
2020-06-23 10:42:47
why i got WA?
i am new in SPOJ.in my solution,first i find out the factorization of prime of n.then count the large fruquency of a prime number.but i got WA.
2019-10-16 12:24:39
hi
2019-06-18 20:55:52
prime factorization + map -- AC in 0.19s
2019-05-29 08:11:50
AC in 1st attempt & also 0.00 sec :)
2018-11-21 11:46:47
intimidating one !
2016-06-09 17:27:11
Nice Que :) AC 0.00s in first Go :D

Sieve is a complete time consuming and O(sqrt(N) ) factorization is fine

Just write the prime factorization of a number and you can easily figure out the solution.

for example : 12 = (2^2) *3 => ans is 2
Expected Complexity is O( sqrt(N)*log(sqrt(N) ) ) => O(sqrt(N)) since n is very small

Last edit: 2016-06-09 17:30:17
2016-02-15 15:46:44 minhthai
very nice problem :) very creative :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.