AMR10C - Square Free Factorization

no tags 

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
[Rampage] Blue.Mary: 2022-08-17 10:01:14

@nayeem2021: It's possible that your ability of reading and understanding problem statement has some problem.

nayeem2021: 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.

Shubham Jadhav: 2020-07-11 10:36:45

Sounds intimidating, but is really easy

shakib19: 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.

zihadboss: 2019-10-16 12:24:39

hi

towhid1zaman: 2019-06-18 20:55:52

prime factorization + map -- AC in 0.19s

roni_roy18: 2019-05-29 08:11:50

AC in 1st attempt & also 0.00 sec :)

koushiq: 2018-11-21 11:46:47

intimidating one !

karthik1997: 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
minhthai: 2016-02-15 15:46:44

very nice problem :) very creative :D


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