서로소 쌍

두 자연수 A, B의 최대공약수를 GCD(A, B), 최소공배수를 LCM(A, B)라고 하자. A와 B가 서로소이면 GCD(A, B) = 1이고, 이때 LCM(A, B) = $A \times B$이다.

자연수 N이 주어질 때 LCM(A, B) = N을 만족하는 서로소인 자연수 쌍 (A, B)는 여러 개일 수 있다. 예를 들어 N = 30이면 (1, 30), (2, 15), (3, 10), (5, 6)의 네 가지가 있다. 순서만 다른 두 쌍은 같은 쌍으로 센다.

N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 구하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어지는 T개의 줄에 각 테스트 케이스의 자연수 N이 한 줄에 하나씩 주어진다. N은 100,000,000 이하이다.

각 테스트 케이스마다 N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 입력 순서대로 한 줄에 하나씩 출력한다.