Problem: You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n.

For example, if n=3, and k=7, then all numbers that are not divisible by 3 are: 1, 2, 4, 5, 7, 8, 10, 11, 13 .... The 7-th number among them is 10.

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases in the input. Next, t test cases are given, one per line.

Each test case is two positive integers n (2 ≤ n ≤ 10^9) and k (1 ≤ k ≤ 10^9).

Output

For each test case print the k-th positive integer that is not divisible by n.

Example

Input


6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1


Output


10
15
1999999999
113
1000000001
1

Solution (in PYTHON3):

Solution:


# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
# sys.setrecursionlimit(10**5)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())

NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
from collections import deque, defaultdict 
import heapq

def bfs(V, E):
	s = set()
	# print('\n'.join(map(str,E.items())))
	num_connected_components = 0 
	for v in V:
		if v in s:
			continue
		q = deque([])
		s.add(v)
		q.append(v)
		while len(q) > 0:
			x = q.popleft()
			for e in E[x]:
				if e not in s:
					s.add(e)
					q.append(e)
			# print(q)
		num_connected_components += 1
	return num_connected_components

def bfs_get_neig(V, get_neig):
	s = set()
	# print('\n'.join(map(str,E.items())))
	num_connected_components = 0 
	for v in V:
		if v in s:
			continue
		q = deque([])
		s.add(v)
		q.append(v)
		while len(q) > 0:
			x = q.popleft()
			for e in get_neig(*x):
				if e not in s:
					s.add(e)
					q.append(e)
			# print(q)
		num_connected_components += 1
	return num_connected_components

# def dfs(V,E):
#   s = set()
#   cnt = 0
#   for v in V:
#       if v in s
# from typing import List, Tuple

def binary_count_smaller(L, x):
	l = 0
	if x < L[0]:
		return 0
	r = len(L)
	while r - l > 1:
		mid = (l+r)//2
		if L[mid] < x:
			l = mid
		else:
			r = mid
	return l + 1
def binary_count_larger(L, x):
	l = 0
	if x > L[-1]:
		return 0
	r = len(L)
	while r - l > 1:
		mid = (l+r)//2
		if L[mid] <= x:
			l = mid
		else:
			r = mid
	return len(L) - (r-1)

def regular_bs(L,x,l=None,r=None):
	l = 0 if l == None else l
	r = len(L) if r == None else r
	while (r-l) > 1:
		m = (r+l)//2
		l = m if L[m] <= x else l
		r = m if L[m] > x else r
	cnt = 0
	return l

from itertools import product

def preprocess():
	nums = dict(zip(sequences,range(10)))
	changes = defaultdict(dict)
	for comb in map(lambda x: ''.join(x), product(*([['0','1']]*7))):
		for seq in sequences:
			a = int(comb,2)
			b = int(seq,2)
			num_changes = bin(a^b).count('1')
			if num_changes == seq.count('1') - comb.count('1'):
				changes[comb][num_changes] = nums[seq]
	return changes


# import StringIO# use for PYPY when lots of prints
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)
from collections import deque
from itertools import product
def bi(x):
	return bin(x)[2:]

def check_no_ghg_row(matrix,n,m):
	for i in range(n):
		black = False
		white = False
		for x in matrix[i]:
			if x == '.' and (not black or white):
				continue
			if x == '#' and black and white:
				return False
			if x == '#' and black:
				continue
			if x == '.' and black:
				white = True
			if x == '#':
				black = True
	return True

def check_no_ghg_col(matrix,n,m):
	for j in range(m):
		black = False
		white = False
		for i in range(n):
			x = matrix[i][j]
			if x == '.' and (not black or white):
				continue
			if x == '#' and black and white:
				return False
			if x == '#' and black:
				continue
			if x == '.' and black:
				white = True
			if x == '#':
				black = True
	return True

def empty_col(matrix,n,m):
	for j in range(m):
		empty = True
		for i in range(n):
			if matrix[i][j] == '#':
				empty=False
				break
		if empty:
			return True
	return False

def empty_row(matrix,n,m):
	for i in range(n):
		empty=True
		for j in range(m):
			if matrix[i][j] == '#':
				empty=False
				break
		if empty:
			return True
	return False


# A = [[],[]]
# def preprocess_tue():
# 	for i in range(2,100001):
# 		orig = i
# 		divisors = [1]
# 		for j in range(2,int(math.sqrt(i))+1):
# 			if i % j == 0:
# 				if i // j > int(math.sqrt(i)) and i // j != orig:
# 					divisors.append(i//j)
# 				if j != orig:
# 					divisors.append(j)
# 		if i != 1 and i != orig:
# 			divisors.append(i)
# 		A.append(divisors)
def find_lcm(num1, num2): 
	if(num1>num2): 
		num = num1 
		den = num2 
	else: 
		num = num2 
		den = num1 
	rem = num % den 
	while(rem != 0): 
		num = den 
		den = rem 
		rem = num % den 
	gcd = den 
	lcm = int(int(num1 * num2)/int(gcd)) 
	return lcm 

def find_lcm_array(A):
	if len(A) == 1:
		return A[0]
	lcm = find_lcm(A[0], A[1] ) 

	for i in range(2, len(A)): 
		lcm = find_lcm(lcm, A[i]) 
	return lcm

class TreeNode:
	def __init__(self,key,left=None,right=None):
		self.left = left if left else None
		self.right = right if right else None
		self.key = key

# MAGIC_NUMBER = 2097152
# NUM_BITS=20
# MAGIC_NUMBER = 16
# NUM_BITS=3

#segment_tree:
# magic_number = 2**(int(math.ceil(math.log(n+1,2)))+1) 
# 	num_bits=len(bi(n))
# 	tree = defaultdict(int)
# 	# tree = [0 for i in range(magic_number)]
# 		if q > 0:
# 			b = bi(q).zfill(num_bits)
# 			i = 1
# 			tree[i]+=1
# 			for c in b:
# 				if c == '0':
# 					i = i*2
# 				else: 
# 					i = 2*i+1
# 				tree[i] += 1
# 		if q < 0:
# 			q = -q
# 			i = 1
# 			while i < magic_number:
# 				tree[i]-=1
# 				if 2*i >= magic_number:
# 					break
# 				if tree[2*i] >= q:
# 					i=2*i
# 				else:
# 					q-=tree[2*i]
# 					i = 2*i+1












def solution(n,k):
	if k%(n-1) == 0:
		return (k//(n-1))*n-1
	return (k//(n-1))*n+k%(n-1)



def prepare_squares():
	L = []
	for i in range(int(math.sqrt(10**7))+1):
		L.append(i**2)
	return L

def main():
	squares = prepare_squares()
	T = read_int()
	for i in range(T):
		n,k = read_int_array()
		x = solution(n,k)

		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			print >>output,str(x)# "Case #"+str(i+1)+':',
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()



'''stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* BITS - THINK HOW TO MASK PROPERLY
	* PERMUTATIONS - PARITY AND CYCLES
	* Think simple, if it becomes over complicated, try to look at it from a different perspective.
	* Have fun!!!
	* TRY FIXING SOMETHING, and then maybe binary search around it.
	* Remember heaps. 
	* Remember how to add a value to a segment when using prefix sum.
		suppose you have an array[1,2,3,4,5] and you want to add 3 to array[1:4]. Then just 
		add 3 to A[1], and decrease 3 from A[4]. Let's look at what happens:
		original prefixsums is 					 [1,3,6,10,15]
		array -> [1,5,3,4,2] and prefix sums are [1,6,9,13,15] 
		As you see, exactly +3 in A[1:4]
		*** The previous method can help checking how many x,y you can choose to get s=x+y from two arrays.
'''
'''
binary search 
	while(r - l > 1) {
		ll mid = l + (r - l) / 2;
		solve(mid);
		ll sum = 0;
		for (int i = 0; i < n; i++)
			sum += b[i];
		if (sum <= k)
			r = mid;
		else
			l = mid;
	}
'''