Junk or Joy

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.

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.