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:
# Notes: We know that every number less than n is indivisible by n. If k is less than n, we just return k. After that, we can try approaching the problem linearly.

# Yay! I found a constant time solution by analyzing the numbers and finding a pattern. I did this by myself with zero external help!!!
def KthNotDivisibleByN(n: int, k: int) -> None:
    if (k < n):
        print(k)
        return
    print(int((k*n - 1)/(n-1)))
    return

# This solution will exceed the given time limit for (2, 1000000000). Invalid
# def KthNotDivisibleByN(n: int, k: int) -> None:
#     if (k < n):
#         print(k)
#         return
#     if (n == 2):
#         print(k*n - 1)
#         return
#     indivisible = []
#     for i in range(n + 1, n*k, n):
#         for j in range(n - 1):
#             indivisible.append(i + j)
#     print(indivisible)
#     print(indivisible[k - n])

test_cases = int(input())

for i in range(test_cases):
    inputs = input().split()
    KthNotDivisibleByN(int(inputs[0]), int(inputs[1]))