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.


-----Examples-----

Input
5
2
4
6
15
20
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$.

Difficulty: HARD
Tags: Number theory

Mathematics

Constructive algorithms

Starter code:

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


import sys
import math

def lowbit(x):
	return x & -x

def read_numbers():
	return [int(x) for x in sys.stdin.readline().strip().split()]

def solve():
	t = read_numbers()[0]
	for _ in range(t):
		num = read_numbers()[0]
		if lowbit(num) == num:
			print(-1)
		else:
			lb = lowbit(num)
			div_res = num // lb
			ans = min(2 * lb, div_res)
			print(ans)
solve()


for T in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(2)
	else:
		h = n & -n
		if h == n:
			print(-1)
		else:
			q = n // h
			if q // 2 < h:
				print(q)
			else:
				print(h * 2)


x = int(input().strip())
for i in range(x):
	n = int(input().strip())
	m = int(n & -n)
	if m == n:
		print('-1')
	elif n % 2 == 1:
		print('2')
	else:
		print(min(n // m, 2 * m))


import sys
input = sys.stdin.readline

def solve(num):
	val = num
	count = 0
	while val % 2 == 0:
		count += 1
		val //= 2
	k1 = 2 ** (count + 1)
	k2 = val
	if k2 - k1 >= 1 and (k2 - k1) % 2 == 1:
		print(k1)
	elif 1 < k2 < k1:
		print(k2)
	else:
		print(-1)
for _ in range(int(input())):
	num = int(input())
	solve(num)


for i in range(int(input())):
	n = int(input())
	m = n & -n
	print('2') if n % 2 == 1 else print(min(n // m, 2 * m) - abs(min(n // m, 2) - 2) * 2)


from collections import defaultdict, deque
import sys
input = lambda : sys.stdin.readline().strip()
test_cases = int(input())
while test_cases > 0:
	test_cases -= 1
	n = int(input())
	copy = n
	if copy % 2 != int(copy % 2):
		print(2)
	else:
		while copy % 2 == 0:
			copy = copy // 2
		if copy == 1:
			print(-1)
		else:
			print(min(copy, 2 * n // copy))


for _ in range(int(input())):
	n = int(input())
	if n & 1:
		print(2)
	else:
		a = n
		while a & 1 == 0:
			a = a >> 1
		if a == 1:
			print(-1)
		elif a * (a + 1) <= 2 * n:
			print(int(a))
		else:
			print(int(2 * (n // a)))


def solve(n):
	k = n
	i = 0
	while k % 2 == 0:
		k = k // 2
		i += 1
	if k == 1:
		return -1
	if k * (k - 1) // 2 < n:
		return k
	else:
		return 1 << i + 1
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n & 1:
		print(2)
	else:
		a = n
		while a & 1 == 0:
			a = a >> 1
		if a == 1:
			print(-1)
		elif a * (a + 1) <= 2 * n:
			print(int(a))
		else:
			print(int(2 * (n // a)))


from collections import Counter, defaultdict, deque, namedtuple
from functools import lru_cache
from typing import List, Dict
import bisect as b
import heapq as h
import math as m

def inti():
	return int(input())

def ints():
	return [int(x) for x in input().split()]

def main_tc():
	n = inti()
	two_part = 1
	odd_part = n
	while odd_part % 2 == 0:
		two_part <<= 1
		odd_part >>= 1
	if odd_part - ((two_part << 1) + 1) >= 0:
		print(two_part << 1)
		return
	if odd_part == 1:
		print(-1)
		return
	print(odd_part)
	return

def main():
	tc = inti()
	for _ in range(tc):
		main_tc()
main()


t = int(input())
for i in range(t):
	n = int(input())
	p = 0
	while n % 2 == 0:
		n //= 2
		p += 1
	if n == 1:
		print(-1)
	elif n < 2 ** (p + 1):
		print(n)
	else:
		print(2 ** (p + 1))


for _ in range(int(input())):
	n = int(input())
	rem = n
	while rem % 2 == 0:
		rem //= 2
	if rem == 1:
		print(-1)
	else:
		print(min(rem, 2 * n // rem))


x = int(input().strip())
for i in range(x):
	n = int(input().strip())
	b = int(n)
	while n % 2 == 0:
		n //= 2
	print('-1') if n == 1 else print(min(n, b * 2 // n))


import math as m
for i in range(int(input())):
	a = int(input())
	b = a
	while a % 2 == 0:
		a //= 2
	b //= a
	if a == 1:
		print(-1)
	else:
		print(min(a, 2 * b))


for t in range(int(input())):
	n = int(input())
	m = n
	while m % 2 == 0:
		m //= 2
	if m == 1:
		print(-1)
	else:
		print(min(m, 2 * n // m))


def count2primes(n):
	number = 0
	prod = 1
	while n % 2 == 0:
		n = n // 2
		number += 1
		prod *= 2
	return (number, prod, n)

def test(n):
	(number, prod, rest) = count2primes(n)
	if number == 0:
		return 2
	if rest == 1:
		return -1
	return min(prod * 2, rest)
T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	print(test(n))


def find(num):
	for i in range(len(powers)):
		if num % powers[i] != 0 and 2 * num % powers[i] == 0:
			return powers[i]
powers = []
for i in range(1, 61):
	powers.append(2 ** i)
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 != 0:
		print(2)
		continue
	if n in powers:
		print(-1)
		continue
	value = find(n)
	if value * (value + 1) / 2 > n:
		value = 2 * n // value
	print(value)


t = int(input())
for i in range(t):
	n = int(input())
	st = 0
	while n % 2 == 0:
		n = n // 2
		st += 1
	if n == 1:
		x = -1
	elif n > 2 ** (st + 1):
		x = 2 ** (st + 1)
	else:
		x = n
	print(x)


for _ in range(int(input())):
	n = int(input())
	if n & n - 1 == 0:
		print(-1)
	elif n % 2 == 1:
		print(2)
	else:
		k = 2
		while n % 2 == 0:
			n //= 2
			k *= 2
		print(min(k, n))


t = int(input())
for _ in range(t):
	n = int(input())
	tmp = n
	ans = 2
	while n % 2 == 0:
		ans *= 2
		n //= 2
	if ans * (ans + 1) // 2 <= tmp:
		print(ans)
	elif n > 1 and n * (n + 1) // 2 <= tmp:
		print(n)
	else:
		print(-1)


for _ in range(int(input())):
	(n, s) = (int(input()), 2)
	x = n
	while x % 2 == 0:
		x //= 2
		s *= 2
	print(-1 if x == 1 else min(s, n * 2 // s))


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		ans = 1
		while n % 2 == 0:
			n = n // 2
			ans *= 2
		if n == 1:
			print(-1)
		else:
			print(min(ans * 2, n))
	else:
		print(2)


import sys
import math
from collections import defaultdict
T = int(input())
for _ in range(T):
	n = int(input())
	k = 1
	while n % 2 == 0:
		n = n // 2
		k *= 2
	if n == 1:
		print('-1')
	else:
		print(min(n, 2 * k))


for _ in range(int(input())):
	n = int(input())
	if n == 2 or n == 4:
		print(-1)
		continue
	if n % 2:
		print(2)
	else:
		t = 1
		while n % 2 == 0:
			n //= 2
			t *= 2
		if n == 1:
			print(-1)
		else:
			print(min(n, 2 * t))


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		z = str(bin(n))[2:]
		x = len(z)
		zn = 0
		for i in range(x // 2):
			if z[-i - 1] == '1':
				zn = 2 ** (i + 1)
				break
		if zn > 0:
			print(zn)
		else:
			while z[-1] == '0':
				z = z[:-1]
			if z == '1':
				print(-1)
			else:
				z = '0b' + z
				print(int(z, 2))
	else:
		print(2)


n = int(input())
while n:
	t = int(input())
	if t % 2 == 1:
		print(2)
	else:
		from math import log
		if t == 2 ** int(log(t, 2)):
			print(-1)
		else:
			p2 = 0
			k = t
			while t % 2 == 0:
				t = t // 2
				p2 = p2 + 1
			print(min(2 ** (p2 + 1), k // 2 ** p2))
	n = n - 1


test = eval(input())
for i in range(test):
	n = eval(input())
	x = 1
	t = n
	while n % 2 == 0:
		x *= 2
		n = n // 2
	tmp = x * (x * 2 + 1)
	if tmp <= t:
		if tmp % (x * 2) == t % (x * 2):
			print(x * 2)
			continue
	if n != 1:
		tmp = n * (n + 1) // 2
		if tmp <= t:
			if tmp % n == t % n:
				print(n)
				continue
	print(-1)