제곱 자유수 인수

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N이 주어질 때, 곱이 N이 되는 1보다 큰 제곱 인수가 없는 인수의 최소 개수를 구합니다.

문제

하지만 아직 끝나지 않았다. 찾은 각 인수는 반드시 제곱 자유수(square-free)여야 한다. 어떤 방식으로 인수분해하든 제곱수인 인수를 갖지 않는 수가 제곱 자유수이다. 물론 1은 인수로 포함할 수 없다.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 다음 $T$ 개 줄에는 각각 정수 $N$ 이 하나씩 주어진다.

각 테스트 케이스마다 제곱 자유수인 인수의 최소 개수를 출력한다.

6은 그대로 6으로 두면 되며, 2x3으로만 더 나뉘고 두 인수 모두 제곱 자유수이므로 인수는 1개다. 8은 모든 인수가 제곱 자유수가 되도록 2x2x2로 인수분해해야 한다.