사탕 봉지

사람들 중에는 실제 과제가 정교하지만 다소 불필요한 이야기에 가려져 있지 않으면 문제를 풀어도 만족하지 못하는 이들이 있다. 그런 사람이라면 이 문제가 바로 당신을 위한 것이다.

지역 사탕 공장의 환경 담당자인 당신의 삶은 비유적으로도, 말 그대로도 달콤하다. 앞으로 더 달콤해질 것이다. 회사의 플라스틱 사용량을 절반으로 줄일 수 있다면 승진시켜 주겠다는 약속을 받았고, 당신은 그렇게 할 계획이다.

현재 공장은 엄청난 양의 플라스틱 포장재를 쓰고 있다. 공장은 매일 $n$가지 맛의 사탕을 생산하며, 맛마다 1부터 $n$까지 번호가 붙어 있고, 각 맛은 따로 봉지에 담긴다. 당신의 아이디어는 봉지 하나에 두 가지 맛을 담아 봉지 수를 절반으로 줄이는 것이다.

하지만 그리 간단하지 않다. $i$번째 맛의 사탕은 항상 $i$개씩 생산되어 하나의 봉지에 담긴다. 맛 $i$와 $j$를 같은 봉지에 담는다면, 그 봉지의 사탕은 어떤 크기의 친구 모임에 공평하고 고르게 나눌 수 있어야 한다. 형식적으로는 $i$와 $j$가 1보다 큰 공약수를 가져야 한다.

일부 맛을 짝지어 같은 봉지에 담고, 나머지 맛은 각자 봉지에 담을 수 있다. 필요한 봉지의 최소 개수는 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 $z$ ($1 \le z \le 5$)가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 공장에서 생산하는 사탕 맛의 가짓수를 나타내는 정수 $n$ ($2 \le n \le 10^{11}$) 하나가 주어진다.

각 테스트 케이스마다 필요한 봉지의 최소 개수를 한 줄에 출력한다.