Square-Free Numbers
시간 제한2초메모리 제한1024 MB
각 N에 대해 곱이 N이 되는 제곱인수가 없는 인수의 최소 개수를 출력한다.
문제
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.
입력
The first line of input is the number of test cases T.
The next T lines each have an integer N.
출력
For each testcase, output the smallest number of square-free factors.
제한
- T ≤ 104
- 2 ≤ N ≤ 106
힌트
6 can be factored as just 6 (further factorable as 2x3 only, and hence square free), a single factor. 8 has to be factored as 2x2x2 so that all factors are square-free.