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: VERY_HARD
Tags: Number theory

Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
primef = [[] for i in range(10 ** 6 + 1)]
for val in range(2, 10 ** 6):
	if primef[val] != []:
		continue
	else:
		for i in range(val, 10 ** 6 + 1, val):
			primef[i].append(val)

def min_possible(a):
	if len(a) == k:
		return sum(a)
	value = 10 ** 8
	for i in range(len(a) - 1):
		for j in range(i + 1, len(a)):
			x = a[:]
			temp = a[i] * a[j]
			x.remove(a[i])
			x.remove(a[j])
			x.append(temp)
			value = min(value, min_possible(x))
	return value

def answer(x, k):
	(s, val) = (0, x)
	all_ = []
	for i in primef[val]:
		p = 0
		while x % i == 0:
			x //= i
			p += 1
		all_.append(i ** p)
	if k - len(primef[val]) >= 0:
		return min(sum(all_) + (k - len(primef[val])), val + (k - 1))
	else:
		return min_possible(all_)
for T in range(int(input())):
	(k, x) = map(int, input().split())
	print(answer(x, k))


from sys import setrecursionlimit
setrecursionlimit(1000000)

def primeFactors(n):
	if n % 2 == 0:
		num.append(1)
		while n % 2 == 0:
			num[-1] *= 2
			n //= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			num.append(1)
			while n % i == 0:
				num[-1] *= i
				n //= i
	if n > 1:
		num.append(n)

def final(l):
	x = len(l)
	if x == k:
		return sum(l)
	ans = float('inf')
	for i in range(x - 1):
		for j in range(i + 1, x):
			num1 = l[:]
			num1.remove(l[i])
			num1.remove(l[j])
			num1.append(l[i] * l[j])
			ans = min(ans, final(num1))
	return ans
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	num = []
	primeFactors(x)
	n = len(num)
	if k >= n:
		print(sum(num) + k - n)
	else:
		print(final(num))


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


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 = 1e+18
	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 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 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
t = int(input())
while t != 0:
	(k, x) = 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


import math

def factorize(n):
	factors = []
	count = 0
	while n % 2 == 0:
		count += 1
		n = n // 2
	if count != 0:
		factors.append(2 ** count)
	count = 0
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			count += 1
			n = n // i
		if count != 0:
			factors.append(i ** count)
		count = 0
	if n > 2:
		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
TC = int(input())
for tc in range(TC):
	(K, X) = 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)


import math
import sys
from functools import partial, reduce
from typing import Dict, List, Sequence, TypeVar
SAMPLE_IN = 'sample.in'
SAMPLE_ANS = 'sample.ans'

def read_ints(f) -> list:
	return [int(x) for x in f.readline().split()]

def read_case(f=sys.stdin):
	return read_ints(f)

def get_primes_until(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	lim = int(math.sqrt(n))
	for i in range(2, lim):
		if not is_prime[i]:
			continue
		for j in range(2 * i, n + 1, i):
			is_prime[j] = False
	primes = [2] + [i for i in range(3, n + 1, 2) if is_prime[i]]
	return primes
PRIMES = get_primes_until(1000000)

def factorize(n, primes=PRIMES):
	powers = []
	x = n
	for p in primes:
		c = 0
		while x % p == 0:
			x //= p
			c += 1
		if c > 0:
			powers.append((p, c))
		if x == 1:
			return powers
	raise ValueError('{} is too big, you need more primes'.format(n))

def solve(n, x) -> tuple:
	if n == 1:
		return x
	powers = factorize(x)
	if len(powers) <= n:
		return n - len(powers) + sum((p ** exp for (p, exp) in powers))
	else:
		factors = [p ** exp for (p, exp) in powers]

		def sum_of_products(groups):
			return sum((reduce(lambda a, b: a * b, group) for group in groups))
		return min((sum_of_products(partition) for partition in partitions_of_size(factors, n)))
T = TypeVar('T')

def build_partition(items: Sequence[T], part_of: Dict[int, int]) -> List[List[T]]:
	num_parts = 1 + max(part_of)
	parts = [[] for _ in range(num_parts)]
	for i in range(len(items)):
		parts[part_of[i]].append(items[i])
	return parts

def partitions_of_size(items, size):
	n = len(items)
	part_of = []

	def f(current_num_parts, index_to_append):
		part_of.append(index_to_append)
		if index_to_append == current_num_parts < size:
			current_num_parts += 1
		max_num_parts = current_num_parts + n - len(part_of)
		if max_num_parts >= size:
			if len(part_of) == n:
				yield build_partition(items, part_of)
			else:
				end = min(size, current_num_parts + 1)
				for i in range(end):
					yield from f(current_num_parts, i)
		part_of.pop()
	return f(0, 0)

def make_submission(fin=sys.stdin, fout=sys.stdout):
	output = partial(print, file=fout)
	n_cases = int(fin.readline())
	for t in range(n_cases):
		case = read_case(fin)
		answer = solve(*case)
		output(answer, file=fout)
import os
if os.getenv('GCJ_LOCAL'):
	with open(SAMPLE_IN) as fin:
		make_submission(fin)
else:
	make_submission()


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 traceback
import math
MAX_INF = 9223372036854775807
INF = 2147483647
SEM_INF = INF // 2
MOD = int(1000000000.0 + 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

	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)

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

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

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


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

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)


from sys import stdin, stdout, stderr, maxsize
tup = lambda : map(int, stdin.readline().split())
I = lambda : int(stdin.readline())
lint = lambda : [int(x) for x in stdin.readline().split()]
S = lambda : stdin.readline().replace('\n', '').strip()
stpr = lambda x: stdout.write(f'{x}' + '\n')
star = lambda x: print(' '.join(map(str, x)))
from math import ceil, floor, gcd
from _collections import defaultdict
from bisect import bisect_left, bisect_right
from itertools import combinations

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):
	ans = maxsize
	if len(arr) == k:
		return sum(arr)
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			t = arr[:]
			t[i] = t[i] * t[j]
			t.remove(t[j])
			ans = min(ans, recur(t))
	return ans
for _ in range(I()):
	(k, x) = tup()
	p = primes(x)
	if len(p) <= k:
		t = k - len(p)
		print(sum(p) + t)
		continue
	print(recur(p))


import sys
pekerja = []

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def faktor(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(factors, arr, pos):
	if pos == len(factors):
		return sum(arr)
	ans = float('inf')
	for i in range(len(arr)):
		arr[i] *= factors[pos]
		ans = min(ans, bruteForce(factors, arr, pos + 1))
		arr[i] //= factors[pos]
	return ans
for j in range(int(input())):
	(k, x) = get_ints()
	factors = faktor(x)
	lenn = len(factors)
	if lenn <= k:
		ans = sum(factors) + k - lenn
	else:
		arr = [1] * k
		ans = bruteForce(factors, arr, 0)
	pekerja.append(ans)
for j in pekerja:
	print(j)


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


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)


import math
from collections import defaultdict

def pp(n):
	l = dict()
	while n % 2 == 0:
		if 2 in l.keys():
			l[2] += 1
		else:
			l[2] = 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in l.keys():
				l[i] += 1
			else:
				l[i] = 1
			n = n // i
	if n > 2:
		l[n] = 1
	return l

def tp(s, k, a):
	ans = float('inf')
	tp = [0 for i in range(s)]
	req = [k - 1 for i in range(s)]
	while tp != req:
		arr = [1 for i in range(k)]
		for i in range(s):
			arr[tp[i]] *= a[i]
		if ans > sum(arr):
			ans = sum(arr)
		for i in range(s - 1, -1, -1):
			if tp[i] < k - 1:
				tp[i] += 1
				break
			else:
				tp[i] = 0
	return ans
for a0 in range(int(input())):
	(k, x) = [int(x) for x in input().split()]
	l = pp(x)
	a = []
	for i in l.keys():
		a.append(i ** l[i])
	if k >= len(a):
		print(sum(a) + k - len(a))
	else:
		print(tp(len(a), k, a))


def multi(arr, fctrs, curr):
	if curr == len(fctrs):
		return sum(arr)
	ans = float('inf')
	for i in range(len(arr)):
		arr[i] *= fctrs[curr]
		ans = min(ans, multi(arr, fctrs, curr + 1))
		arr[i] //= fctrs[curr]
	return ans
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	fctrs = []
	for i in range(2, int(x ** 0.5) + 1):
		if x % i == 0:
			fctrs.append(1)
			while x % i == 0:
				fctrs[-1] *= i
				x //= i
	if x > 1:
		fctrs.append(x)
	if k >= len(fctrs):
		ans = sum(fctrs) + k - len(fctrs)
	else:
		arr = [1] * k
		ans = multi(arr, fctrs, 0)
	print(ans)


def solve(k, x):
	fact = []
	i = 2
	while i * i <= x:
		if x % i == 0:
			fact.append(1)
		while x % i == 0:
			x //= i
			fact[-1] *= i
		i += 1
	if x != 1:
		fact.append(x)
	if k >= len(fact):
		return sum(fact) + k - len(fact)
	arr = [1] * k
	return partition(fact, 0, arr, k, float('inf'))

def partition(fact, i, arr, k, ans):
	if i == len(fact):
		return min(ans, sum(arr))
	for j in range(len(arr)):
		arr[j] *= fact[i]
		ans = min(ans, partition(fact, i + 1, arr, k, ans))
		arr[j] //= fact[i]
	return ans
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	print(solve(k, x))


import sys
from math import sqrt
import math
from collections import defaultdict as df

def ini():
	return int(sys.stdin.readline())

def inp():
	return map(int, sys.stdin.readline().strip().split())

def li():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()

def p(n):
	d = df(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def check(l, n):
	if len(l) == n:
		return sum(l)
	maxi = float('inf')
	for i in range(len(l) - 1):
		for j in range(i + 1, len(l)):
			t = l.copy()
			t.remove(l[i])
			t.remove(l[j])
			t.append(l[i] * l[j])
			maxi = min(maxi, check(t, n))
	return maxi
for i in range(ini()):
	(n, k) = inp()
	d = p(k)
	l = [value ** d[value] for value in d.keys()]
	if n >= len(l):
		print(sum(l) + (n - len(l)))
	else:
		print(check(l, n))


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 solve(i=0):
	if i == len(pfs):
		return sum(a)
	mini = float('inf')
	for j in range(k):
		a[j] *= pfs[i]
		mini = min(mini, solve(i + 1))
		a[j] //= pfs[i]
	return mini
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	ox = x
	pfs = []
	for i in range(2, int(x ** 0.5) + 1):
		c = 0
		while x % i == 0:
			x //= i
			c += 1
		if c > 0:
			pfs.append(i ** c)
	if x > 1:
		pfs.append(x)
	if len(pfs) <= k:
		print(sum(pfs) + k - len(pfs))
		continue
	a = [1] * k
	print(solve())


from math import sqrt
from collections import Counter
from itertools import combinations as com

def get(l, k):
	if len(l) == k:
		return sum(l)
	n = len(l)
	m = 1000000000000
	for i in range(n - 1):
		for j in range(i + 1, n):
			a = l.copy()
			a.remove(l[i])
			a.remove(l[j])
			a.append(l[i] * l[j])
			m = min(m, get(a, k))
	return m
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	n = x
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	cc = Counter(l)
	l = [i ** cc[i] for i in cc]
	if len(l) > k:
		print(get(l, k))
	else:
		r = sum(l) + (k - len(l))
		print(r)


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

def brute_force(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_force(pos + 1, arr, factors))
		arr[i] //= factors[pos]
	return ans
for tc in range(int(input())):
	(K, X) = map(int, input().split())
	factors = factorize(X)
	lenn = len(factors)
	if lenn <= K:
		ans = sum(factors) + K - lenn
	else:
		arr = [1] * K
		ans = brute_force(0, arr, factors)
	print(ans)


import math

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

def combo(pos, factors, lst):
	if pos == len(factors):
		return sum(lst)
	ans = math.inf
	for i in range(len(lst)):
		lst[i] *= factors[pos]
		ans = min(ans, combo(pos + 1, factors, lst))
		lst[i] /= factors[pos]
	return ans
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	lst = factors(x)
	if len(lst) <= k:
		print(int(sum(lst) + (k - len(lst))))
	else:
		lst = k * [1]
		ans = combo(0, factors(x), lst)
		print(int(ans))


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


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


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')

def find(a, ind):
	global ans
	if ind == len(d1):
		ans = min(ans, sum(a))
		return
	prev = a[:]
	for j in range(k):
		a[j] *= d1[ind]
		find(a, ind + 1)
		a = prev[:]
t = int(input())
for i in range(t):
	(k, x) = map(int, input().split())
	d = defaultdict(int)
	if x % 2 == 0:
		while x % 2 == 0:
			d[2] += 1
			x //= 2
		d[2] = pow(2, d[2])
	for j in range(3, int(math.sqrt(x)) + 1, 2):
		if x % j == 0:
			while x % j == 0:
				d[j] += 1
				x //= j
			d[j] = pow(j, d[j])
	if x > 2:
		d[x] = x
	d1 = list(d.values())
	if len(d1) <= k:
		ans = sum(d1)
		ans += k - len(d1)
	else:
		ans = 10 ** 9
		for j in range(k):
			a = [1] * k
			a[j] *= d1[0]
			find(a, 1)
	print(ans)


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)


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())):
	(n, x) = list(map(int, input().split()))
	factors = []
	k = n
	h = x
	for i in range(2, int(h ** 0.5) + 1):
		if h % i == 0:
			cnt = 0
			while h % i == 0:
				h //= i
				cnt += 1
			factors.append(i ** cnt)
	if h != 1:
		factors.append(h)
	m = len(factors)
	if m == k:
		print(sum(factors))
	elif m < k:
		print(sum(factors) + k - m)
	else:
		arr = [1] * k
		ans = bruteforce(0, arr, factors)
		print(ans)


from math import *

def algorithm_u(ns, m):

	def visit(n, a):
		ps = [[] for i in range(m)]
		for j in range(n):
			ps[a[j + 1]].append(ns[j])
		return ps

	def f(mu, nu, sigma, n, a):
		if mu == 2:
			yield visit(n, a)
		else:
			for v in f(mu - 1, nu - 1, (mu + sigma) % 2, n, a):
				yield v
		if nu == mu + 1:
			a[mu] = mu - 1
			yield visit(n, a)
			while a[nu] > 0:
				a[nu] = a[nu] - 1
				yield visit(n, a)
		elif nu > mu + 1:
			if (mu + sigma) % 2 == 1:
				a[nu - 1] = mu - 1
			else:
				a[mu] = mu - 1
			if (a[nu] + sigma) % 2 == 1:
				for v in b(mu, nu - 1, 0, n, a):
					yield v
			else:
				for v in f(mu, nu - 1, 0, n, a):
					yield v
			while a[nu] > 0:
				a[nu] = a[nu] - 1
				if (a[nu] + sigma) % 2 == 1:
					for v in b(mu, nu - 1, 0, n, a):
						yield v
				else:
					for v in f(mu, nu - 1, 0, n, a):
						yield v

	def b(mu, nu, sigma, n, a):
		if nu == mu + 1:
			while a[nu] < mu - 1:
				yield visit(n, a)
				a[nu] = a[nu] + 1
			yield visit(n, a)
			a[mu] = 0
		elif nu > mu + 1:
			if (a[nu] + sigma) % 2 == 1:
				for v in f(mu, nu - 1, 0, n, a):
					yield v
			else:
				for v in b(mu, nu - 1, 0, n, a):
					yield v
			while a[nu] < mu - 1:
				a[nu] = a[nu] + 1
				if (a[nu] + sigma) % 2 == 1:
					for v in f(mu, nu - 1, 0, n, a):
						yield v
				else:
					for v in b(mu, nu - 1, 0, n, a):
						yield v
			if (mu + sigma) % 2 == 1:
				a[nu - 1] = 0
			else:
				a[mu] = 0
		if mu == 2:
			yield visit(n, a)
		else:
			for v in b(mu - 1, nu - 1, (mu + sigma) % 2, n, a):
				yield v
	n = len(ns)
	a = [0] * (n + 1)
	for j in range(1, m + 1):
		a[n - m + j] = j - 1
	return f(m, n, 0, n, a)
for _ in range(int(input())):
	(k, x) = [int(i) for i in input().split()]
	facts = []
	for i in range(2, int(sqrt(x)) + 1):
		if x % i == 0:
			y = 1
			while x % i == 0:
				y *= i
				x /= i
			facts.append(y)
	if x > 1:
		facts.append(x)
	s = sum(facts)
	m = len(facts)
	rem_1 = max(0, k - m)
	if rem_1:
		s = int(sum(facts))
		print(s + rem_1)
		continue
	ans_best = 10 ** 18
	for s in algorithm_u(facts, k):
		ans = 0
		for subset in s:
			y = 1
			for elem in subset:
				y *= elem
			ans += y
		ans_best = int(min(ans_best, ans))
	print(ans_best)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7

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(factors, arr, pos):
	if pos == len(factors):
		return sum(arr)
	ans = float('inf')
	for i in range(len(arr)):
		arr[i] *= factors[pos]
		ans = min(ans, bruteForce(factors, arr, pos + 1))
		arr[i] //= factors[pos]
	return ans
for _ in range(int(input())):
	(k, x) = get_ints()
	factors = factorize(x)
	lenn = len(factors)
	if lenn <= k:
		ans = sum(factors) + k - lenn
	else:
		arr = [1] * k
		ans = bruteForce(factors, arr, 0)
	print(ans)


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) = map(int, input().split())
	arr = factorize(x)
	if len(arr) < k:
		print(sum(arr) + k - len(arr))
	else:
		print(recur(arr))


from fractions import Fraction
import bisect
import os
import io
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate
from queue import Queue

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def swap(arr, a, b):
	(arr[a], arr[b]) = (arr[b], arr[a])

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

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

def solve(K, X):
	factors = getPrimeFactors(X)
	lenn = len(factors)
	if K >= lenn:
		return sum(factors) + K - lenn
	else:
		partition = [1] * K
		return partitions(0, partition, factors)
for _ in range(iinput()):
	(K, X) = rinput()
	print(solve(K, X))


def factorise(num):
	factors = []
	for i in range(2, int(num ** 0.5) + 1):
		if num % i == 0:
			power = 0
			while num % i == 0:
				power += 1
				num = num // i
			factors.append(i ** power)
	if num != 1:
		factors.append(num)
	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] = arr[i] // factors[pos]
	return ans
t = int(input())
for _ in range(t):
	(work, days) = map(int, input().split())
	factors = factorise(days)
	n = len(factors)
	if n == work:
		print(sum(factors))
	elif n < work:
		total = sum(factors) + work - n
		print(total)
	else:
		arr = [1] * work
		ans = bruteforce(0, arr, factors)
		print(ans)


import math as mt
MAXN = 1000001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(2, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	p = getFactorization(x)
	s = list(set(p))
	s.sort()
	le = len(s)
	ans = 0
	ans1 = k - 1 + x
	if le <= k:
		for i in s:
			ans += i ** p.count(i)
		ans += k - le
	else:
		nl = [[1 for u in range(k)]]
		for i in s:
			v = i ** p.count(i)
			newl = []
			for y in nl:
				for u in range(k):
					op = y.copy()
					op[u] *= v
					newl.append(op)
			nl = newl.copy()
		ans = sum(nl[0])
		for i in nl:
			ans = min(ans, sum(i))
	print(min(ans, ans1))


from math import gcd

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

def reduce(factors, k):

	def func(cur):
		if cur == len(factors):
			ans[0] = min(ans[0], sum(partitions))
			return
		for i in range(k):
			partitions[i] *= factors[cur]
			func(cur + 1)
			partitions[i] = partitions[i] // factors[cur]
	partitions = [1 for i in range(k)]
	ans = [float('inf')]
	func(0)
	return ans[0]
for _ in range(int(input())):
	(k, x) = map(int, input().split())
	factors = getFactors(x)
	if len(factors) <= k:
		print(sum(factors) + k - len(factors))
	else:
		print(reduce(factors, k))