K-good

Description:

Input:

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.

Each test case consists of one line with an integer $$$n$$$ ($$$2 \leq n \leq 10^{18}$$$).

Output:

For each test case, print a line with a value of $$$k$$$ such that $$$n$$$ is $$$k$$$-good ($$$k \geq 2$$$), or $$$-1$$$ if $$$n$$$ is not $$$k$$$-good for any $$$k$$$. If there are multiple valid values of $$$k$$$, you can print any of them.

Sample Input:

5
2
4
6
15
20

Sample Output:

-1
-1
3
3
5

Note:

$$$6$$$ is a $$$3$$$-good number since it can be expressed as a sum of $$$3$$$ numbers which give different remainders when divided by $$$3$$$: $$$6 = 1 + 2 + 3$$$.

$$$15$$$ is also a $$$3$$$-good number since $$$15 = 1 + 5 + 9$$$ and $$$1, 5, 9$$$ give different remainders when divided by $$$3$$$.

$$$20$$$ is a $$$5$$$-good number since $$$20 = 2 + 3 + 4 + 5 + 6$$$ and $$$2,3,4,5,6$$$ give different remainders when divided by $$$5$$$.