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:
def read_tokens():
    return input().strip().split(' ')


def read_ints():
    return [int(s) for s in read_tokens()]


T = int(input())


def solve(n: int, k: int) -> int:
    bad = 0
    good = 10**18
    while good - bad > 1:
        m = (good+bad) // 2
        if (m - m // n) >= k:
            good = m
        else:
            bad = m
    return good
    # # (1...n-1)   # 1 2
    # # N
    # # n+1...2n-1  # 4 5
    # # 2N
    # # 2n+1...3n-1 # 7 8
    # # 3N
    # # 3n+1..4n-1  # 10 11
    # # ...
    # # numbers_in_range = n-1
    # range_idx = (k // n) + 1 # 4
    # maxim_k = (n-1)*range_idx
    # minim_k = (n-1)*range_idx - (n-1)
    # for el in ma

    # return range_idx*n+1


for test in range(T):
    n, k = read_ints()
    ans = solve(n, k)
    print(ans)