Junk or Joy

양의 정수 $k$가 주어진다. $n^2 - k \cdot p^m = 1$을 만족하고 $p$가 소수인 양의 정수 순서쌍 $(n, p, m)$의 개수를 구하라. 그러한 순서쌍이 무한히 많으면 $-1$을 출력한다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 100$)가 주어진다. 각 테스트 케이스는 정수 $k$ ($1 \le k \le 10^9$) 하나가 적힌 한 줄로 이루어진다.

각 테스트 케이스마다 $n^2 - k \cdot p^m = 1$을 만족하고 $p$가 소수인 양의 정수 순서쌍 $(n, p, m)$의 개수를 출력한다. 순서쌍이 무한히 많으면 $-1$을 출력한다.

첫 번째 테스트 케이스에서 $k = 5$이면 가능한 순서쌍은 $(4, 3, 1)$, $(6, 7, 1)$, $(9, 2, 4)$뿐이다. 두 번째 테스트 케이스에서 $k = 22$이면 조건을 만족하는 순서쌍이 없다.