시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB97483643.902%

문제

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

예제 입력 1

2
6
8

예제 출력 1

1
3

힌트

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.