Gru wants to distribute $N$ bananas to $K$ minions on his birthday.
Gru does not like to just give everyone the same number of bananas, so instead, he wants to distribute bananas in such a way that each minion gets a $distinct$ amount of bananas. That is, no two minions should get the same number of bananas.
Gru also loves $gcd$. The higher the $gcd$, the happier Gru and the minions get. So help Gru in distributing the bananas in such a way that each Minion gets a distinct amount of bananas and gcd of this distribution is highest possible. Output this maximum gcd. If such a distribution is not possible output $-1$.
Note: You have to distribute $all$ $N$ bananas. 

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase consists of a single line of input, which has two integers: $N, K$. 

-----Output:-----
For each testcase, output in a single line the maximum gcd or -1.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N, K \leq 10^9$

-----Sample Input:-----
1
6 3

-----Sample Output:-----
1

-----EXPLANATION:-----
The only possible distribution is $[1, 2, 3]$. So the answer is 1.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
for _ in range(int(input())):
	(k, n) = map(int, input().split())
	k1 = k
	summ = n * (n + 1) // 2
	if n > 44720 or summ > k:
		print(-1)
	else:
		fact = []
		for i in range(1, int(math.sqrt(k)) + 1):
			if k % i == 0:
				fact += [i, k // i]
		fact.sort()
		for i in fact:
			if i >= summ:
				print(k // i)
				break


def factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
			if x // i != i:
				result.append(x // i)
		i += 1
	return result
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = factors(n)
	an = -1
	for i in a:
		c = i * k * (k + 1) // 2
		if c <= n:
			an = max(an, i)
	print(an)


from sys import stdin
from functools import reduce

def factors(n):
	return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	m = k * (k + 1) // 2
	if m > n:
		print(-1)
	else:
		arr = factors(n)
		arr = sorted(arr, reverse=True)
		for ele in arr:
			if n // ele >= m:
				print(ele)
				break


import math
for _ in range(int(input())):
	lis = list(map(int, input().split()))
	n = lis[0]
	k = lis[1]
	temp = k * (k + 1) // 2
	if n < temp:
		print(-1)
	elif k == 1:
		print(n)
	else:
		flag = 1
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				if n // i >= temp:
					flag = max(flag, i)
				k = n // i
				if n // k >= temp:
					flag = max(flag, k)
		print(flag)


import math

def printDivisors(n):
	l = []
	x = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				x.append(i)
			else:
				x.append(i)
				l.append(int(n / i))
	return x + l[::-1]
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	kk = printDivisors(n)
	x = k * (k + 1) // 2
	if n < x:
		print(-1)
	else:
		op = 10 ** 9
		for i in kk:
			if n // i >= x:
				op = min(op, n // i)
		print(n // op)


import math

def find_fac(fac, n):
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			if n // i != i:
				fac.append(n // i)
			fac.append(i)
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	temp = k * (k + 1) // 2
	fac = []
	find_fac(fac, n)
	fac.sort()
	flag = 0
	for i in range(len(fac) - 1, -1, -1):
		if n // fac[i] >= temp:
			break
		flag += 1
	if flag == len(fac):
		print(-1)
	else:
		print(fac[i])


def factors(n):
	i = 1
	z = []
	while i <= int(n ** 0.5) + 1:
		if n % i == 0:
			if n // i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def sumOfFirstN(n):
	return n * (n + 1) // 2

def case():
	(n, k) = map(int, input().split())
	z = factors(n)
	z.sort()
	if sumOfFirstN(k) > n:
		print(-1)
		return
	ans = 1
	for gcd in z:
		if n - gcd * sumOfFirstN(k) < 0:
			break
		if (n - gcd * sumOfFirstN(k)) % gcd == 0:
			ans = max(ans, gcd)
	print(ans)
for _ in range(int(input())):
	case()


from math import sqrt
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(fact, i) = ([], 1)
	while i <= sqrt(n):
		if n % i == 0:
			if n // i != i:
				fact.append(n // i)
			fact.append(i)
		i += 1
	tot = k * (k + 1) // 2
	mx = -1
	for i in fact:
		if i >= tot:
			mx = max(mx, n // i)
	print(mx)


def factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
			if x // i != i:
				result.append(x // i)
		i += 1
	return result
for _ in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	Sum = K * (K + 1) / 2
	X = N / Sum
	if X < 1:
		print(-1)
	else:
		List = factors(N)
		List.sort()
		if len(List) == 1:
			print(1)
		else:
			for i in range(len(List)):
				if List[i] == X:
					print(List[i])
					break
				elif List[i] > X:
					print(List[i - 1])
					break


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n < k * (k + 1) // 2:
		print(-1)
		continue
	tmp = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if n // i == i:
				tmp.append(i)
			else:
				tmp.append(i)
				tmp.append(n // i)
	tmp.sort()
	tmp = tmp[::-1]
	ans = 1
	s = k * (k + 1) // 2
	for x in tmp:
		if n // x >= s:
			print(x)
			break


def factor(N):
	Z = []
	N = int(N)
	p = int(N ** 0.5)
	for i in range(1, p):
		if N % i == 0:
			Z.append(i)
			Z.append(int(N / i))
	Z.sort()
	return Z
x = int(input())
for y in range(x):
	(i, j) = list(map(int, input().split()))
	if j * (j + 1) / 2 > i:
		print(-1)
	else:
		p = j * (j + 1) / 2
		b = int(i / p)
		A = factor(i)
		s = len(A)
		if b in A:
			print(b)
		else:
			for y in range(1, s):
				if A[y - 1] <= b < A[y]:
					print(A[y - 1])


def solve(n, k):
	r = -1
	sk = (k + 1) * k // 2
	d = 1
	while d ** 2 <= n:
		if n % d == 0:
			g1 = d
			if sk * g1 <= n:
				r = max(r, g1)
			g2 = n // d
			if sk * g2 <= n:
				r = max(r, g2)
		d += 1
	return r
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	z = k * (k + 1) // 2
	if z > n:
		print(-1)
	elif z == n:
		print(1)
	else:
		ans = 1
		for i in range(1, int(n ** 0.5) + 1, 1):
			if n % i == 0:
				if i >= z:
					ans = max(n // i, ans)
				elif n // i >= z:
					ans = max(i, ans)
		print(ans)


from math import sqrt
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	(f, c) = ([], 1)
	while c <= sqrt(n):
		if n % c == 0:
			if n // c != c:
				f.append(n // c)
			f.append(c)
		c += 1
	s = k * (k + 1) // 2
	m = -1
	for c in f:
		if c >= s:
			m = max(m, n // c)
	print(m)


def biggest(number, ans):
	last = 1
	for i in range(2, int(number ** 0.5) + 1):
		if number % i == 0:
			if number // i >= ans:
				last = max(last, i)
			k = number // i
			if number // k >= ans:
				last = max(last, k)
	return last
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	summ = k * (k + 1)
	summ //= 2
	if summ > n:
		print(-1)
	elif k == 1:
		print(n)
	else:
		ans = biggest(n, summ)
		print(ans)


from math import sqrt, floor

def T(N):
	A = []
	for i in range(1, floor(sqrt(N)) + 1):
		if N % i == 0:
			if N // i == i:
				A.append(i)
			else:
				A.append(i)
				A.append(N // i)
	return A
a = int(input())
for i in range(a):
	(N, K) = map(int, input().split())
	A = T(N)
	if N < K * (K + 1) // 2:
		print(-1)
	else:
		B = []
		for j in A:
			if N // j >= K * (K + 1) // 2:
				B.append(j)
		b = max(B)
		print(b)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	sm = k * (k + 1) // 2
	fact = set()
	sq = int(n ** 0.5)
	sq += 100
	for i in range(1, sq):
		if n % i == 0:
			fact.add(i)
			fact.add(n // i)
	res = -1
	for f in fact:
		if f * sm <= n:
			res = max(res, f)
	print(res)


for _ in range(int(input())):
	(n, res) = map(int, input().split())
	ans = res * (res + 1) // 2
	ans = n // ans
	if ans == 0:
		print(-1)
	else:
		cnt = 1
		for x in range(1, int(pow(n, 0.5)) + 1):
			if n % x != 0:
				continue
			if x <= ans and x > cnt:
				cnt = x
			if n // x <= ans and n // x > cnt:
				cnt = n // x
		print(cnt)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	Z = K * (K + 1) // 2
	Z = N // Z
	if Z == 0:
		print(-1)
	else:
		r = 1
		for x in range(1, int(pow(N, 0.5)) + 1):
			if N % x != 0:
				continue
			if x <= Z and x > r:
				r = x
			if N // x <= Z and N // x > r:
				r = N // x
		print(r)


def fac(n):
	se = set()
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			se.add(i)
			se.add(n // i)
	return sorted(list(se))

def pro(k):
	return k * (k + 1) // 2
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	if n < pro(m):
		print(-1)
		continue
	arr = fac(n)
	arr = arr[1:]
	ans = [1]
	for j in arr:
		p = n // j
		if p < pro(m):
			break
		else:
			ans.append(j)
	print(max(ans))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	root = int(n ** 0.5)
	min_sum = k * (k + 1) // 2
	gcd = -1
	for i in range(1, root + 1):
		if n % i == 0:
			sum = n // i
			if sum >= min_sum:
				gcd = max(gcd, i)
			if i >= min_sum:
				gcd = max(gcd, sum)
	print(gcd)


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	minions = k * (k + 1) // 2
	if minions > n:
		print(-1)
		continue
	cur_ans = 1
	i = 1
	limit = n ** 0.5
	while i <= limit:
		if n % i == 0:
			if n - i * minions >= 0 and (n - i * minions) % i == 0:
				cur_ans = max(cur_ans, i)
			ti = n // i
			if n - ti * minions >= 0 and (n - ti * minions) % ti == 0:
				cur_ans = max(cur_ans, ti)
		i += 1
	print(cur_ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	sm = k * (k + 1) // 2
	if n < sm:
		print(-1)
		continue
	m = 1
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if n // i >= sm:
				m = max(m, i)
			x = n // i
			if n // x >= sm:
				m = max(m, x)
	print(m)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	val = k * (k + 1) // 2
	ans = -1
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			rem = n // i
			if rem >= val:
				ans = max(ans, i)
			if i >= val:
				ans = max(ans, rem)
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = k * (k + 1) // 2
	x = n // a
	ans = -1
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if n // i <= x:
				ans = max(ans, n // i)
			elif i <= x:
				ans = max(ans, i)
			else:
				break
	print(ans)


def gcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	b = int(n / (k * (k + 1) / 2))
	if b == 0:
		print('-1')
	else:
		r = 1
		x = 1
		while x * x <= n:
			if n % x != 0:
				x += 1
				continue
			if x <= b and x > r:
				r = x
			if n // x <= b and n // x > r:
				r = n // x
			x = x + 1
		i = 1
		while i < k:
			a.append(r * i)
			i += 1
		l = n - r * (k * (k - 1) // 2)
		a.append(l)
		result = a[0]
		for i in a[1:]:
			result = gcd(result, i)
		print(result)


from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = -1
	p = k * (k + 1) // 2
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0 and n - i * p >= 0 and ((n - i * p) % i == 0):
			ans = max(ans, i)
		t = n // i
		if n % t == 0 and n - t * p >= 0 and ((n - t * p) % t == 0):
			ans = max(ans, t)
	print(ans)


from math import sqrt, ceil
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	x = n // (k * (k + 1) // 2)
	ans = -1
	for i in range(1, ceil(sqrt(n) + 1), 1):
		if i > x:
			break
		if n % i == 0:
			if i <= x and i > ans:
				ans = i
			if n // i <= x and n // i > ans:
				ans = n // i
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = -1
	p = k * (k + 1) // 2
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if i * p <= n and (n - i * p) % i == 0:
				ans = max(ans, i)
			q = n // i
			if p * q <= n and (n - q * p) % q == 0:
				ans = max(ans, q)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = -1
	l = []
	for i in range(int(n ** 0.5) + 1, 0, -1):
		if n % i == 0:
			l += [i]
			l += [n // i]
	l.sort(reverse=True)
	for i in l:
		if n // i >= k * (k + 1) // 2:
			ans = i
			break
	print(ans)


import os, sys
from io import BytesIO, IOBase

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
import math
for i in range(ii()):
	(n, k) = mi()
	if k * (k + 1) // 2 > n:
		print(-1)
	elif k == 1:
		print(n)
	else:
		a = k * (k + 1) // 2
		f = 0
		s = n // a
		while s:
			if n % s == 0:
				print(s)
				break
			if s > 100000:
				a += 1
				s = n // a
			else:
				s -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	S = k * (k + 1) // 2
	if n >= S:
		div = []
		for d in range(1, 40000):
			if d * d == n:
				div.append(d)
				break
			if d * d > n:
				break
			if n % d == 0:
				div.append(d)
				div.append(n // d)
		guess = n // S
		if n % guess == 0:
			print(guess)
		else:
			ans = 1
			for i in div:
				if ans < i < guess:
					ans = i
			print(ans)
	else:
		print('-1')


from math import *
t = int(input())
for y in range(t):
	(m, n) = map(int, input().split())
	s = n * (n + 1) // 2
	r = m // s
	l = 1
	ans = -1
	for i in range(int(sqrt(m)), 0, -1):
		if m % i == 0 and i <= r:
			ans = max(ans, i)
			if m // i <= r:
				ans = max(ans, m // i)
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	s = k * (k + 1) // 2
	u = n // s
	if s > n:
		print(-1)
	elif u <= int(n ** 0.5):
		while n % u != 0:
			u -= 1
		print(u)
	else:
		j = int(n / u)
		while j < n ** 0.5 and n % j != 0:
			j += 1
		if j == int(n ** 0.5) + 1 and int(n ** 0.5) != n ** 0.5 or (j == int(n ** 0.5) and int(n ** 0.5) == n ** 0.5):
			j = int(n / u)
			while n % j != 0:
				j -= 1
			print(j)
		else:
			print(n // j)


from math import sqrt
for t in range(int(input())):
	(n, k) = map(int, input().split())
	c = k * (k + 1) // 2
	f = []
	for i in range(1, int(sqrt(n)) + 2):
		if not n % i:
			f += [i, n // i]
	for i in reversed(sorted(f)):
		if i * c <= n:
			print(i)
			break
	else:
		print(-1)