Junk or Joy

You are given a positive integer $k$. Count the tuples of positive integers $(n, p, m)$ such that $n^2 - k \cdot p^m = 1$ and $p$ is a prime number. If there are infinitely many such tuples, print $-1$.

The first line contains the number of test cases $t$ ($1 \le t \le 100$). Each test case is described by a single line containing one integer $k$ ($1 \le k \le 10^9$).

For each test case, print the number of positive integer tuples $(n, p, m)$ satisfying $n^2 - k \cdot p^m = 1$ with $p$ prime, or $-1$ if there are infinitely many of them.

In the first test case, for $k = 5$, the only possible tuples are $(4, 3, 1)$, $(6, 7, 1)$, and $(9, 2, 4)$. In the second test case, for $k = 22$, no tuples exist.