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 sys import stdin
def quant_div(inicio,fim, n=7):
    if int(inicio/n) != inicio/n:
        ndiv = int(fim/n) - int(inicio/n)
    else:
        ndiv = int(fim/n) - int(inicio/n) + 1
    return ndiv

def quant_not_div(inicio,fim, n):
    return (fim-inicio+1) - quant_div(inicio, fim, n)
    

def not_div(n = 3,k = 7):
    count = 0
    inicio = 1
    fim = k # 7
    while count != k:
        count += quant_not_div(inicio, fim, n)
        i = inicio
        inicio = fim+1
        fim = fim + quant_div(i,fim,n)

    return inicio-1

t = int(stdin.readline().replace('\n', '').replace(' ', '')) 

result = []
for i in range(t):
    n,k = stdin.readline().split(' ')
    k = k.replace('\n', '').replace(' ', '')
    result += [not_div(n=int(n),k=int(k))]

for r in result:
    print(r)