SPOJ.com - Problem AMR10C

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 test case, output the smallest number of square-free factors.

Constraints

T ≤ 10⁴
2 ≤ N ≤ 10⁶

Example

Input:
2
6
8

Output:
1
3

Submit solution!

hide comments

< Previous 1 2 3 Next >

	Shashank Tiwari: 2015-12-12 21:58:53 Question can be restated as : Given a number 'N' , we need to find minimum number of divisors of N such that : 1 ) N = D_1 X D_2 X ...... X D_i (Here we have N as product of 'i' divisors) 2) The count of such divisors used i.e. here it is 'i' should be minimum. 3) There should not be no perfect square which should divide any of these above divisors. 4) Hence 1 is not allowed to be considered as any divisor because of point (3). Example : Lets take n =24 . We can have : 1) 24 = 24 but 4 divides 24 and 4 is perfect square . So , Rejected. 2) 24= 12 X 2 but 4 again divides 12 so , this is also rejected. 3) 24 = 6 X 4 ; This is also rejected as 4 divides 4. 4) 24 = 6 X 2 X 2 ; Now this is acceptable. And this is what we will find that is minimum such possible divisors used satisfying above conditions so mentioned. Hence ans for 24 is 3. Lets take another example. N= 7. Here 7=7 is satisfied. So ans =1. Lets take another example . N=6. 6=6 ; so ans =1. Lets take another example . N=25. Here 25 =25 cannot be taken as 25 itself divides 25 and is a perfect square. But 25 = 5 X 5 can be taken . Hence ans = 2. Lets take N=44 , then 44 = 22 X2 , hence ans =2 . Note that 44 = 4 X 11 is not valid. Also , 44 = 11 X 2 X 2 is long and not of minimum length. Hope this helps.
	:.Mohib.:: 2015-08-03 20:53:20 Great...!!
	Madhav: 2015-03-29 14:08:14 good concept!!
	Malinga: 2015-01-09 09:32:09 Sieve+fast I/O...AC in 1.19 sec
	Anubhav Balodhi : 2014-12-30 09:35:03 Mathematical one ^_^
	BLANKRK: 2014-06-25 22:40:56 nice !!! :)
	abhishek nagpal: 2013-09-01 12:03:17 what will be the answer for 44? 2 or 3?
	Spar!k: 2013-02-05 00:13:02 sieve just makes it slower. sqrt(n) is ok
	Branfili: 2012-12-15 22:04:39 @Kennard 2, because 36=6*6

Submit solution!

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