시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 34 | 12 | 9 | 33.333% |
You are given a positive integer $k$. Find the number of tuples of positive integers $(n, p, m)$ such that $n^2 - k \cdot p^m = 1$ and $p$ is a prime number, or report that an infinite number of such tuples exists.
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.
The only line of each test case contains a single integer $k$ ($1 \le k \le 10^9$).
For each test case, print the number of positive integer tuples $(n, p, m)$ such that $n^2 - k \cdot p^m = 1$ and $p$ is a prime, or $-1$ if there's an infinite number of them.
2 5 22
3 0
In the first example test case, for $k = 5$, the only possible tuples are $(4, 3, 1)$, $(6, 7, 1)$, and $(9, 2, 4)$.
In the second example test case, for $k = 22$, no possible tuples exist.