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: interview

Starter code:

Solutions:
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)

from math import sqrt

for _ in range(int(input())):
 
 n, k = list(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 sorted(fact):
  if i>=tot:
   mx = n//i
   break
   
 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

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%i==0 and c<=n):
   an=max(an,i)
 print(an)

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




#print(factor(10))
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])


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])
  


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**.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)

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%i==0 and c<=n):
   an=max(an,i)
 print(an)

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%i==0 and c<=n):
   an=max(an,i)
 print(an)

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)

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)

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)

# Thanks to Shelam

t=int(input())


for _ in range(t):
 n,k=map(int,input().split())
 ans=-1
 l=[]
 for i in range(int(n**.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 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)
 else:
  if 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)
'''
for _ in range(int(input())):
    n=int(input())
    lis=list(map(int,input().split()))
    q=int(input())
    s=''
    for i in range(n):
     if (lis[i]&1)==0:
      s+='0'
     else:
      s+='1'
    for _ in range(q):
     x=list(map(int,input().split()))
     l=x[0]
     r=x[1]
     temp='1'*((r+1)-l)
     if temp==s[l-1:r]:
      print("ODD")
     else:
      print("EVEN")
'''

'''
n=int(input())
lis=list(map(int,input().split()))
m=lis[0]
c=lis[1]
c1=0
c2=0
for i in range(n):
    temp=0
    t=list(map(int,input().split()))
    temp=t[1]-m*t[0]-c
    if temp>0:
     c1+=t[2]
    else:
     c2+=t[2]
print(max(c1,c2))
'''