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:
import math
def solve_test_case():
	#let's binary search over the answer ok?
	INPUT = input().split()
	n = int(INPUT[0])
	k = int(INPUT[1])
	#this makes sense so far right ye
	low = 0
	high = 10000000000

	while low < high:
		mid = math.floor((low+high)/2)
		number = mid - math.floor(mid/n)
		#does above make sense for number, we subtract the number of numbers divisible by k 
		if number >= k:
			high = mid
		else:
			low=mid+1
	print(low)
	#this is all the code do u need b seearch for this or could u do it normally wdym is this all the code no u wrote that could u do it normally tho normally?
	#wdym normally
  #without b search 
def main():
	t = int(input());
	for i in range(t):
		solve_test_case() 
		#ooops this is wrong, ok it should work now
		#try it

    #u forgot to call the function lolololololol oh it worked

main()