K-good
Contest: CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1900
Tags: constructive algorithms, math, number theory

We say that a positive integer $$$n$$$ is $$$k$$$-good for some positive integer $$$k$$$ if $$$n$$$ can be expressed as a sum of $$$k$$$ positive integers which give $$$k$$$ distinct remainders when divided by $$$k$$$.

Given a positive integer $$$n$$$, find some $$$k \geq 2$$$ so that $$$n$$$ is $$$k$$$-good or tell that such a $$$k$$$ does not exist.

Input format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
5
2
4
6
15
20

Example output:
-1
-1
3
3
5

Editorial:
$$$n$$$ is $$$k$$$-good if and only if
• $$$n \geq 1 + 2 + \ldots + k = \frac{k(k+1)}{2}$$$.
• $$$n \equiv 1 + 2 + \ldots + k \equiv \frac{k(k+1)}{2} \pmod{k}$$$.
It is clear that both conditions are necessary, and it turns out they're sufficient too since $$$\frac{k(k+1)}{2} + m \cdot k$$$ is attainable for any integer $$$m \geq 0$$$ by repeatedly adding $$$k$$$ to one of the terms in the sum $$$1 + 2 + \ldots + k$$$.
Note that, if $$$k$$$ is even, the second condition is $$$n \equiv \frac{k}{2} \pmod{k}$$$, which is true if and only if $$$2n$$$ is a multiple of $$$k$$$ but $$$n$$$ is not a multiple of $$$k$$$. So all $$$k$$$ which divide $$$2n$$$ but do not divide $$$n$$$ satisfy the second condition, and we want the smallest of them in order to have the best chance of satisfying the first condition. The smallest of such $$$k$$$ is $$$k_1 = 2^{\nu_2(n)+1}$$$, i. e. the smallest power of $$$2$$$ that does not divide $$$n$$$. We can compute $$$k_1$$$ in $$$O(\log n)$$$ (or in $$$O(1)$$$ with some architecture-specific functions) and check if it satisfies the first condition.
If it doesn't, consider $$$k_2 = \frac{2n}{k_1}$$$. Note that $$$k_2$$$ is odd, and therefore the second condition is satisfied since $$$k_2$$$ is a divisor of $$$n$$$. Since $$$k_1$$$ did not satisfy the condition, we have $$$k_1(k_1+1) > 2n \implies k_2 < k_1+1 \implies k_2 \leq k_1-1$$$ (since $$$k_2$$$ is odd), so:
$$$$$$ \frac{k_2(k_2+1)}{2} \leq \frac{k_2 \cdot k_1}{2} = n $$$$$$
So $$$k_2$$$ satisfies the first condition.
Note that $$$k_2$$$ is only a valid answer if $$$k_2 \neq 1$$$. If $$$k_2 = 1$$$, then we have that $$$n$$$ is a power of $$$2$$$, and in this case there is no answer since all odd candidates of $$$k$$$ must be odd divisors of $$$n$$$, of which there is only $$$1$$$, and the smallest even candidate for $$$k$$$ was $$$k_1 = 2n$$$, which does not work. So we have to answer $$$-1$$$.