K-good (Codeforces 1656D)
Tags: 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: 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.

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

Sample Inputs:
5
2
4
6
15
20

Sample Outputs:
-1
-1
3
3
5

Solution (Python):
for i in [*open(0)][1:]:
    n = int(i)
    m = n & -n
    a = n // m
    print('2' if n & 1 else min(a, 2 * m) - (min(a, 2) & 1) * 2)

Solution (Python):
for i in [*open(0)][1:]:
    n = int(i)
    m = n & -n
    a = n // m
    print('2' if n & 1 else min(a, 2 * m) - (min(a, 2) & 1) * 2)

Solution (Python):
for i in [*open(0)][1:]:
    n = int(i)
    m = n & -n
    a = n // m
    print('2' if n & 1 else min(a, 2 * m) - abs(min(a, 2) - 2) * 2)