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 ceil
from queue import LifoQueue


def print_sol(c, sol):
    print('Case #{}: {}'.format(c, sol))


def rd_int():
    return int(input())


def rd_str():
    return input()


def rd_str_lst():
    return input().split(' ')


def sp_str_lst():
    return list(input())


def rd_int_lst():
    return [int(i) for i in rd_str_lst()]


def sp_int_lst():
    return [int(i) for i in sp_str_lst()]


def dfs(g, i, v):
    """
    recursive post order dfs
    Args:
        g: array of graph nodes
        i: node to traverse
        v: visited array

    Returns: a post order dfs of graph g
    """
    v[i] = True
    for j in g[i]:
        if not v[j]:
            dfs(g, j, v)

    print(i)


def dfs_iter(g, i, n):
    v = [False] * n
    stack = LifoQueue()
    stack.put(i)
    while stack.not_empty:
        u = stack.get()
        v[u] = True
        print(u)
        for i in g[u]:
            if not v[i]:
                stack.put(i)


def hapi(g, i, d, va, da, sa):
    va[i] = True
    d += 1
    da[i] = d
    sa[i] = 1
    for j in g[i]:
        if not va[j]:
            hapi(g, j, d, va, da, sa)
            sa[i] += sa[j]


def hapi_iter(g, i, n):
    va = [False] * n
    da = [0] * n
    sa = [0] * n
    stack = LifoQueue()
    stack.put(i)
    while stack.not_empty:
        u = stack.get()
        va[u] = True
        print(u)
        for i in g[u]:
            if not va[i]:
                stack.put(i)


def main():
    t = rd_int()

    for c in range(1, t + 1):
        n, k = rd_int_lst()

        s = ceil(k * (n / (n - 1)) - 1)

        print(s)


if __name__ == '__main__':
    main()