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 collections import defaultdict as dc
from heapq import *
import math
from bisect import bisect_left,bisect
#bisect gives x and p[x] is element greater than it and out of bound for last one 
#p[x-1] gives equal or smaller and no error for any element.
import sys
from collections import deque as dq
from heapq import heapify,heappush,heappop
mod=10**9 +7
def sinp():
    p=str(input())
    return p
def inp(): 
    p=int(input())
    return p
def line():
    p=list(map(int,input().split()))
    return p
def read_mat():
    n=inp()
    a=[]
    for i in range(n):
        a.append(line())
    return a
def digit(n):
    s=str(n)
    p=0
    for i in s:
        p+=(int(i))**2
    return p
def check(p,i,j):
    z=i+(j-i)//2
    if p[z]-p[i] == p[j]-p[z]:
        #print(p[z]-p[i],p[j]-p[z])
        return j-i
    return 0
def solve(a,b):
    ans=b
    if b%(a-1)==0:
        ans=ans+(b//(a-1))-1
    else:
        ans=ans+(b//(a-1))
    return ans
    
for test in range(inp()):
    a,b=line()
    # n=len(a)
    l=solve(a,b)
    print(l)