A manufacturing project consists of exactly $K$ tasks. The board overviewing the project wants to hire $K$ teams of workers — one for each task. All teams begin working simultaneously.
Obviously, there must be at least one person in each team. For a team of $A$ workers, it takes exactly $A$ days to complete the task they are hired for. Each team acts independently, unaware of the status of other teams (whether they have completed their tasks or not), and submits their result for approval on the $A$-th day.
However, the board approves the project only if all $K$ teams complete their tasks on the same day — it rejects everything submitted on any other day. The day after a team finds out that its result was rejected, it resumes work on the same task afresh. Therefore, as long as a team of $A$ workers keeps getting rejected, it submits a new result of their task for approval on the $A$-th, $2A$-th, $3A$-th day etc.
The board wants to hire workers in such a way that it takes exactly $X$ days to complete the project. Find the smallest number of workers it needs to hire.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $K$ and $X$.

-----Output-----
For each test case, print a single line containing one integer — the smallest required number of workers.

-----Constraints-----
- $1 \le T \le 40$
- $2 \le K, X \le 10^6$

-----Example Input-----
2
2 3
2 6

-----Example Output-----
4
5

-----Explanation-----
Example case 1: We can hire a team of $3$ workers for task $1$ and $1$ worker for task $2$. The one-man team working on task $2$ completes it and submits the result for approval on each day, but it is rejected on the first and second day. On the third day, the team working on task $1$ also completes their task, so the project gets approved after exactly $3$ days.
Example case 2: We can hire a team of $3$ workers for task $1$ and a team of $2$ workers for task $2$.

Difficulty: interview

Starter code:

Solutions:
from math import log2;
import bisect;
from bisect import bisect_left,bisect_right
import sys;
from math import gcd,sqrt
sys.setrecursionlimit(10**7)
from collections import defaultdict
inf=float("inf")
# n=int(input())
# n,m=map(int,input().split())
# l=list(map(int,input().split()))
def get_factors(x):
 if x==1:
  return [];
 sqrta=int(sqrt(x))+1
 for i in range(2,sqrta):
  if x%i==0:
   return [i]+get_factors(x//i)
 return [x]
def min_generator(fac,k,index,new_list):
 if index==len(fac):
  return sum(new_list)
 mina=inf;
 for i in range(0,min(index+1,len(new_list))):
  new_list[i]*=fac[index]
  theta=min_generator(fac,k,index+1,new_list)
  if theta<mina:
   mina=theta;
  new_list[i]//=fac[index]
 return mina;
def fun(k,x):
 dict=defaultdict(lambda :1)
 factors=get_factors(x)
 for i in factors:
  dict[i]*=i;
 if len(dict)==k:
  print(sum(dict.values()))
  return;
 if len(dict)<k:
  suma=sum(dict.values())
  left=k-len(dict)
  suma+=left;
  print(suma)
  return;
 if k==1:
  print(x)
  return;
 fac=list(dict.values())

 new_list=[1]*k
 theta=min_generator(fac,k,0,new_list)
 print(theta)
for i in range(int(input())):
 k,x=map(int,input().split())
 fun(k,x)

# cook your dish here
def factors(n):
 factor=[]
 for i in range(2,int(n**(1/2))+1):
  cnt=0
  if n%i==0:
   while n%i==0:
    cnt+=1
    n=n//i
   factor.append(i**cnt)
 if n!=1:
  factor.append(n)
 return factor
def bruteforce(pos,arr,factors):
 if pos==len(factors):
  return sum(arr)
  
 ans=float('inf')
 
 for i in range(len(arr)):
  arr[i]*=factors[pos]
  ans=min(ans,bruteforce(pos+1,arr,factors))
  arr[i]//=factors[pos]
 return ans
  
for _ in range(int(input())):
 k,n=list(map(int,input().split()))
 fac=factors(n)
 if len(fac)==k:
  print(sum(fac))
 elif len(fac)<k:
  print(sum(fac)+k-len(fac))
 else:
  arr=[1]*k
  d=bruteforce(0,arr,fac)
  print(d)


# cook your dish here

def factorize(n):
 fact=[]
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   c=0
   while n%i==0:
    c+=1
    n//=i
   fact.append(i**c)
 if n!=1:
  fact.append(n)
  
 return fact

def brute(pos,ar,fact):
 if pos==len(fact):
  return sum(ar)
 ans=float('inf')
 
 for i in range(len(ar)):
  ar[i]*=fact[pos]
  ans=min(ans,brute(pos+1,ar,fact))
  ar[i]//=fact[pos]
  
 return ans
 
t=int(input())

while(t>0):
 
 k,x=map(int,input().split())
 fact=factorize(x)
 lenn=len(fact)
 
 if lenn <=k:
  
  ans= sum(fact)+k-lenn
 else:
  ar=[1]*k
  ans=brute(0,ar,fact)
 print(ans)
 t-=1

def all_pcombo(arr,factors,pos):
 if pos==len(factors):
  return sum(arr)

 ans=float('inf')

 for i in range(len(arr)):
  arr[i]*=factors[pos]
  ans=min(ans,all_pcombo(arr,factors,pos+1))
  arr[i]//=factors[pos]

 return ans

def factorization(n):
 factors=[]
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   cnt=0
   while n%i==0:
    cnt+=1
    n//=i
   factors.append(i**cnt)

 if n>1:
  factors.append(n)
 return factors

def solve():
 k,x=map(int,input().split())
 factors=factorization(x)
 len_=len(factors)

 ans=0
 if len_<=k:
  ans=sum(factors) + k-len_
 else:
  arr=[1]*k
  ans=all_pcombo(arr,factors,0)

 print(ans)


t=int(input())
while t>0:
 solve()
 t-=1

def all_pcombo(arr,factors,pos):
 if pos==len(factors):
  return sum(arr)

 ans=float('inf')

 for i in range(len(arr)):
  arr[i]*=factors[pos]
  ans=min(ans,all_pcombo(arr,factors,pos+1))
  arr[i]//=factors[pos]

 return ans

def factorization(n):
 factors=[]
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   cnt=0
   while n%i==0:
    cnt+=1
    n//=i
   factors.append(i**cnt)

 if n>1:
  factors.append(n)
 return factors

def solve():
 k,x=map(int,input().split())
 factors=factorization(x)
 len_=len(factors)

 ans=0
 if len_<=k:
  ans=sum(factors) + k-len_
 else:
  arr=[1]*k
  ans=all_pcombo(arr,factors,0)

 print(ans)


t=int(input())
while t>0:
 solve()
 t-=1

# cook your dish here
import sys
sys.setrecursionlimit(10000000)


def primes(x):
 f = []
 i = 2
 while i * i <= x:
  if x % i == 0:
   t = 1
   while x % i == 0:
    x //= i
    t *= i
   f.append(t)
  i += 1
 if x > 1:
  f.append(x)
 return f


def recur(arr):
 if len(arr) == k:
  return sum(arr)
 answer = float('inf')
 for i in range(len(arr) - 1):
  for j in range(i + 1, len(arr)):
   temp = arr[:]
   temp.remove(arr[i])
   temp.remove(arr[j])
   temp.append(arr[i] * arr[j])
   answer = min(answer, recur(temp))
 return answer


for _ in range(int(input())):
 k, X = map(int, input().split())
 p = primes(X)
 if k >= len(p):
  print(sum(p) + (k - len(p)))
  continue
 print(recur(p))

# cook your dish here
import math
def factorize(n):
 factors=[]
 for i in range(2,int(n**0.5)+1):
  if(n%i==0):
   cntr=0
   while(n%i==0):
    cntr+=1
    n//=i
   factors.append(i**cntr)
 if n!=1:
  factors.append(n)
 return factors

def brtueforce(pos,arr,factors):
 if pos==len(factors):
  return sum(arr)
 ans=float('inf')
 for i in range(len(arr)):
  arr[i]*=factors[pos]
  ans=min(ans,brtueforce(pos+1,arr,factors))
  arr[i]//=factors[pos]

 return ans


def solve():
 #n=int(input())
 
 k,x=map(int,input().split())
 #s=input()
 #l=list(map(int,input().split()))
 #l1=list(map(int,input().split()))
 #flag=0
 
 factors=factorize(x)

 lenn=len(factors)

 if lenn<=k:

  ans=sum(factors) + k-lenn
 else:
  arr=[1]*k
  ans=brtueforce(0,arr,factors)

 print(ans)

 





t=int(input())
for i in range(t):
 solve()

def factorizing(n):
 factor = []
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   count = 0
   while n%i==0:
    count += 1
    n //= i
   factor.append(i**count)
 
 if (n!=1):
  factor.append(n)
 return factor


def getans(a,f,p):
 if p==len(f):
  return sum(a)
 
 ans = float('inf')
 
 for i in range(len(a)):
  a[i] *= f[p]
  ans = min(ans,getans(a,f,p+1))
  a[i] //= f[p]
 
 return ans

T = int(input())

while(T):
 
 T -= 1
 
 k,x = map(int, input().split())
 
 factors = factorizing(x)
 
 if len(factors)<=k:
  ans = sum(factors) + k-len(factors)
 else:
  a = [1]*k
  ans = getans(a,factors, 0)
 
 print(ans)

def find_div(x):
 b=[]
 e=int(x**0.5)+1
 for i in range(2,e):
  if x%i==0:
   c=0
   while x%i==0:
    c+=1
    x=x//i
   b.append(i**c)
 if x!=1:
  b.append(x)
 return b 
 
def solve(a,div,pos):
 if pos==len(div):
  return sum(a)
 ans=2**30
 for i in range(len(a)):
  a[i]*=div[pos]
  ans=min(ans,solve(a,div,pos+1))
  a[i]=a[i]//div[pos]
 return ans
 
 
t=int(input())
for _ in range(t):
 k,x=map(int,input().split())
 div=find_div(x)
 if len(div)<=k:
  ans=sum(div)+k-len(div)
 else:
  a=[1]*k
  ans=solve(a,div,0)
 print(ans) 

def factorize(n):
 factors=[]
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   cnt=0
   while n%i==0:
    cnt+=1
    n//=i
   factors.append(i**cnt)
 if n!=1:
  factors.append(n)
 return factors

def brute(pos,arr,factors):
 if pos==len(factors):
  return sum(arr)
 ans = float('inf')
 for i in range(len(arr)):
  arr[i]*=factors[pos]
  ans=min(ans,brute(pos+1,arr,factors))
  arr[i]//=factors[pos]
 return ans

t = int(input())
while t:
 k,x=map(int,input().split())
 factors=factorize(x)
 if len(factors)<=k:
  ans=sum(factors)+k-len(factors)
 else:
  arr=[1]*k
  ans=brute(0,arr,factors)
 print(ans)
 t-=1

def factorize(n):
 factors=[]
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   cnt=0
   while n%i==0:
    cnt+=1
    n//=i
   factors.append(i**cnt)
 if n!=1:
  factors.append(n)
 return factors

def brute(pos,arr,factors):
 if pos==len(factors):
  return sum(arr)
 ans = float('inf')
 for i in range(len(arr)):
  arr[i]*=factors[pos]
  ans=min(ans,brute(pos+1,arr,factors))
  arr[i]//=factors[pos]
 return ans

t = int(input())
while t:
 k,x=map(int,input().split())
 factors=factorize(x)
 if len(factors)<=k:
  ans=sum(factors)+k-len(factors)
 else:
  arr=[1]*k
  ans=brute(0,arr,factors)
 print(ans)
 t-=1

def factorize(n):
 factors=[]
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   cntr=0
   while n%i==0:
    cntr+=1
    n//=i
   factors.append(i**cntr)
 if n!=1:
  factors.append(n)

 return factors

def bruteForce(pos,arr,factors):
 if pos==len(factors):
  return sum(arr)

 ans=float('inf')

 for i in range(len(arr)):
  arr[i]*=factors[pos]
  ans=min(ans,bruteForce(pos+1,arr,factors))
  arr[i]//=factors[pos]

 return ans

def __starting_point():
 t=int(input())

 while(t != 0):
  
  k,x=list(map(int, input().split()))
  factors=factorize(x)
  lenn=len(factors)

  if lenn<=k:
   ans=sum(factors)+k-lenn

  else:
   arr=[1]*k
   ans=bruteForce(0,arr,factors)

  print(ans)

  t=t-1


__starting_point()

import traceback;
import math;

MAX_INF = 9223372036854775807
INF = 2147483647
SEM_INF = INF // 2
MOD = int(1e9 + 7)


class HELPER:
 tmplst = []
 pntr = 0
 outPutStream = ""

 def __init__(self):
  pass

 def __next__(self):
  if self.pntr == -1 or self.pntr == len(self.tmplst):
   self.tmplst = input().split(" ")
   self.pntr = 0
  ret = self.tmplst[self.pntr]
  self.pntr += 1

  return ret

 def nextInt(self):
  return int(next(self))

 def nextFloat(self):
  return float(next(self))

 def nextLine(self):
  return input()

 def readArray(self, n):
  l = []
  for x in range(0, n):
   l.append(self.nextInt())
  return l

 def getIntArray(self, s):
  l = []
  s = s.split(" ")
  for x in range(0, len(s)):
   l.append(int(s[x]))

  return l

 # Printing Arena

 def printArray(self, a, nextLine):
  for x in a:
   sc.write("{} ".format(x))
  if nextLine:
   self.writeln()

 def writeln(self, s):
  self.outPutStream += (str(s) + "\n")

 def write(self, s):
  self.outPutStream += str(s)

 def flush(self):
  print(self.outPutStream)
  outPutStream = ""


sc = HELPER()


def writeln(s=""):
 sc.writeln(s)


def write(s):
 sc.write(s)


"""Code Starts Here"""


def getFactorList(n):
 l = [];
 p = 0
 while n % 2 == 0:
  p += 1
  n = n // 2
 l.append(int(math.pow(2,p)))

 x = 3
 while x <= math.sqrt(n):
  p = 0
  while n % x == 0:
   n = n // x
   p += 1
  if p != 0:
   l.append(int(math.pow(x,p)))
  x += 2

 if n > 2:
  l.append(n)

 return l


def getMinRecur(l, a, pos):
 if(pos == len(l)):
  return sum(a)
 ans = float('inf')
 for x in range(0,len(a)):
  a[x] *= l[pos]
  ans = min(ans,getMinRecur(l,a,pos + 1))
  a[x] //= l[pos]

 return ans


def getMinAns(l,k):
 ans = 0
 if k == len(l):
  ans = sum(l)
 elif k > len(l):
  more = k - len(l)
  ans = more + sum(l)
 else:
  arr = [1] * k
  ans = getMinRecur(l,arr,0)
 return ans


def testCase():
 k = sc.nextInt(); day = sc.nextInt()
 l = getFactorList(day)

 ans = getMinAns(l,k)
 ans = min(ans,day + k - 1)
 writeln(ans)
 pass


"""Code Ends Here"""


def main():
 t = int(input())
 # t = 1
 while t > 0:
  testCase()
  t -= 1
 sc.flush()


try:
 def __starting_point():
  main()
except:
 print("Error Occured")
 traceback.print_exc()

__starting_point()

def brute(ind,arr,factors):
 if ind==len(factors):
  return sum(arr)
 ans=10000000000000
 for i in range(len(arr)):
  arr[i]*=factors[ind]
  ans=min(ans,brute(ind+1,arr,factors))
  arr[i] //= factors[ind]
 return ans

def factorize(x):
 factors=[]
 for i in range(2,int(x**0.5)+1):
  if x%i==0:
   count=0
   while x%i==0:
    count+=1
    x //= i
   factors.append(i**count)
 if x!=1:
  factors.append(x)
 return factors


t=int(input())
for _ in range(t):
 k,x=map(int,input().split())
 factors=factorize(x)
 if len(factors)<=k:
  print(sum(factors)+k-len(factors))
 else:
  arr = [1]*k
  print(brute(0,arr,factors))

# cook your dish here
try:
 MAX = 1000005
 prime = [True] * MAX
 fact = [list() for i in range(MAX)]

 for i in range(2, MAX):
  if prime[i]:
   for j in range(i, MAX, i):
    prime[j] = False
    fact[j].append(i)

 def solve(arr, i, k):
  if i >= len(arr):
   return sum(k)
  z = float('inf')
  for j in range(len(k)):
   k[j] *= arr[i]
   z = min(z, solve(arr, i + 1, k))
   k[j] //= arr[i]
  return z

 t = int(input())
 for i in range(t):
  k, x = map(int, input().split())
  temp = []
  for y in fact[x]:
   p = x
   z = 1
   while p % y == 0:
    p //= y
    z *= y
   temp.append(z)
  if k >= len(fact[x]):
   print(sum(temp) + k - len(temp))
  else:
   print(solve(temp, 0, [1] * k))

except EOFError as e : pass

# cook your dish here


def primeFactors(n):
 factors = []
 cnt = 0
 if n%2 == 0:
  while n%2 == 0:
   cnt += 1
   n = n//2

  factors.append(2**cnt)
 
 for i in range(3,int(n**0.5)+1,2):
  cnt = 0
  if n%i == 0:
   
   while n%i == 0:
    cnt += 1
    n = n//i

   factors.append(i**cnt)
 if n != 1:
  factors.append(n)
  
 return factors
 
def minSum(arr,k):
 if len(arr) == k:
  return sum(arr)
 
 ans = 1e18
 for i in range(len(arr)-1):
  temp = []
  for j in range(i+1,len(arr)):
   temp = [arr[i]*arr[j]] + arr[:i] + arr[i+1:j] + arr[j+1:]
  
   ans = min(ans,minSum(temp,k))
 
 return ans
 
TC = int(input())
for tc in range(TC):
 k, x = list(map(int,input().strip().split()))
 
 factors = primeFactors(x)
 
 if len(factors) <= k:
  print(sum(factors) + k-len(factors))
 else:
  print(minSum(factors,k))


# cook your dish here
import sys
sys.setrecursionlimit(10000000)

def primeFactors(n):
 factors = []
 cnt = 0
 if n%2 == 0:
  while n%2 == 0:
   cnt += 1
   n = n//2

  factors.append(2**cnt)
 
 for i in range(3,int(n**0.5)+1,2):
  cnt = 0
  if n%i == 0:
   
   while n%i == 0:
    cnt += 1
    n = n//i

   factors.append(i**cnt)
 if n != 1:
  factors.append(n)
  
 return factors
 
def minSum(arr,k):
 if len(arr) == k:
  return sum(arr)
 
 ans = 1e18
 for i in range(len(arr)-1):
  temp = []
  for j in range(i+1,len(arr)):
   temp = [arr[i]*arr[j]] + arr[:i] + arr[i+1:j] + arr[j+1:]
  
   ans = min(ans,minSum(temp,k))
 
 return ans
 
TC = int(input())
for tc in range(TC):
 k, x = list(map(int,input().strip().split()))
 
 factors = primeFactors(x)
 
 if len(factors) <= k:
  print(sum(factors) + k-len(factors))
 else:
  print(minSum(factors,k))


def factorize(n):
 factors = []
 for i in range(2, int(n**0.5)+1):
  if n % i == 0:
   cntr = 0
   while n % i == 0:
    cntr += 1
    n //= i
   factors.append(i**cntr)
 if n != 1:
  factors.append(n)
 return factors
 
def recur(arr):
 if len(arr)==k:
  return sum(arr)
 res = float('inf')
 for i in range(len(arr)-1):
  for j in range(i+1,len(arr)):
   temp=arr[:]
   temp.remove(arr[i])
   temp.remove(arr[j])
   temp.append(arr[i]*arr[j])
   res = min(res,recur(temp))
 return res

for i in range(int(input())):
 k,x=list(map(int,input().split()))
 arr = factorize(x)
 if len(arr)<k:
  print(sum(arr)+k-len(arr))
 else:
  print(recur(arr))
 
 


import sys
sys.setrecursionlimit(10000000)


def primes(x):
 f = []
 i = 2
 while i * i <= x:
  if x % i == 0:
   t = 1
   while x % i == 0:
    x //= i
    t *= i
   f.append(t)
  i += 1
 if x > 1:
  f.append(x)
 return f


def recur(arr):
 if len(arr) == k:
  return sum(arr)
 answer = float('inf')
 for i in range(len(arr) - 1):
  for j in range(i + 1, len(arr)):
   temp = arr[:]
   temp.remove(arr[i])
   temp.remove(arr[j])
   temp.append(arr[i] * arr[j])
   answer = min(answer, recur(temp))
 return answer


for _ in range(int(input())):
 k, X = list(map(int, input().split()))
 p = primes(X)
 if k >= len(p):
  print(sum(p) + (k - len(p)))
  continue
 print(recur(p))



def prime(n):
 ans = []
 i = 2
 while (i*i <= n):
  if n % i == 0:
   temp1 = 1
   while (n % i == 0):
    n //= i
    temp1 *= i
   ans.append(temp1)
  i += 1
 if n>1:
  ans.append(n)
 return ans

def recur(arr,k):
 if len(arr) == k:
  return sum(arr)
 ans = float('inf')
 for i in range(len(arr)-1):
  for j in range(i+1, len(arr)):
   temp = arr[:]
   temp.remove(arr[i])
   temp.remove(arr[j])
   temp.append(arr[i]*arr[j])
   ans = min(ans, recur(temp,k))
 return ans

tc = int(input())
for i in range(tc):
 k, x = list(map(int,input().split()))
 p = prime(x)
 if len(p) <= k:
  print(sum(p)+k-len(p))
 else:
  print(recur(p,k))


import sys
sys.setrecursionlimit(10000000)
def prime(n):
 ans = []
 i = 2
 while (i*i <= n):
  if n % i == 0:
   temp1 = 1
   while (n % i == 0):
    n //= i
    temp1 *= i
   ans.append(temp1)
  i += 1
 if n>1:
  ans.append(n)
 return ans

def recur(arr,k):
 if len(arr) == k:
  return sum(arr)
 ans = float('inf')
 for i in range(len(arr)-1):
  for j in range(i+1, len(arr)):
   temp = arr[:]
   temp.remove(arr[i])
   temp.remove(arr[j])
   temp.append(arr[i]*arr[j])
   ans = min(ans, recur(temp,k))
 return ans

tc = int(input())
for i in range(tc):
 k, x = list(map(int,input().split()))
 p = prime(x)
 if len(p) <= k:
  print(sum(p)+k-len(p))
 else:
  print(recur(p,k))


import math


def primeFactors(n):
 d = {}
 while n % 2 == 0:
  n = n // 2
  if 2 in d:
   d[2] += 1 
  else:
   d[2] = 1 
 for i in range(3,int(math.sqrt(n))+1,2):
  while n % i== 0:
   if i in d:
    d[i] += 1 
   else:
    d[i] = 1 
   n = n // i
 if n > 2:
  if n in d:
   d[n] += 1 
  else:
   d[n] = 1
 
 return d
 
def get_all_combs(arr, left):
 nonlocal g
 if not left:
  g.append(sum(arr))
 else:
  new = left.pop()
  for i in range(len(arr)):
   newarr = arr.copy()
   newarr[i] *= new 
   get_all_combs(newarr, left.copy())
 


for test in range(int(input())):
 k, x = list(map(int, input().split()))
 d = primeFactors(x)
 
 if k < len(d):
  p = [item**d[item] for item in d]
  xo = [1]*k
  g = []
  get_all_combs(xo, p)
  
  print(min(g))
  continue
 
 c2 = 0
 for item in d:
  c2 += item**d[item]
 diff = k - len(d)
  
 c2 += diff
 
 print(c2)