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 \dots$. The $7$-th number among them is $10$.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 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 \le n \le 10^9$) and $k$ ($1 \le k \le 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

Difficulty: introductory

Starter code:

Solutions:
from sys import *
from collections import *
from math import *

input = stdin.readline

tc = int(input())
for tcase in range(tc):
	n, k = map(int, input().split())
	lo = 1
	hi = 10 ** 19
	ans = -1
	while (lo <= hi):
		mid = (lo + hi) // 2
		divi = mid - mid // n
		if (divi >= k):
			ans = mid
			hi = mid - 1
		else:
			lo = mid + 1
	print(ans)

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    k -= 1
    print(k//(n-1)*n+k % (n-1)+1)


import math 
for i in range(int(input())):
    n,k=list(map(int,input().split()))
    e=math.ceil(k/(n-1))-1
    print(k+e)


t = int(input())
for _ in range(t):
	n, k = map(int, input().split())
	print(n * ((k-1) // (n-1)) + ((k-1) % (n-1)) + 1)

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    num = k // (n - 1)
    if k % (n - 1) == 0:
        ans = num * n - 1
    else:
        ans = num * n + k % (n - 1)
    print(ans)

for t in range(int(input())):
    n, k = list(map(int, input().split()))
    if k % (n - 1) == 0:
        print(k // (n - 1) * n - 1)
    else:
        print(k // (n - 1) * n + k % (n - 1))

def f(x, n):
    return x // n

def ff(l, r, n):
    return f(r, n) - f(l - 1, n)

for _ in range(int(input())):
    # n = int(input())
    # arr = list(map(int, input().split()))
    n, k = list(map(int, input().split()))
    k -= 1
    s = 1
    while k > 0:
        nk = ff(s, s + k, n)
        s += k
        k = nk
        if s % n == 0:
            s -= 1
        if k == 1:
            k = 0
            s += 1
            if s % n == 0:
                s += 1

    print(s)


t = int(input())
for _ in range(t):
    n, k = map(int, input().split())

    ans = n*(k//(n-1))
    if k%(n-1)==0:
        ans -= 1
    else:
        ans += k%(n-1)

    print(ans)

t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    k -= 1
    out = (k % (n - 1))
    k //= (n - 1)
    out += k * n
    out += 1
    print(out)


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    print(k+(k-1)//(n-1))


for tc in range(int(input())):
    n, k = [int(s) for s in input().split()]
    k -= 1
    print(k // (n-1) * n + k % (n-1) + 1)


for _ in range(int(input())):
    n,k=map(int,input().split())
    lo=0 
    hi=10**20
    def check(mi):
        return mi-mi//n>=k 
    while lo<=hi:
        mi=(lo+hi)//2 
        if check(mi):
            ans=mi 
            hi=mi-1 
        else:
            lo=mi+1 
    print(ans)

import math
for _ in range(int(input())):
	n,k=list(map(int,input().split()))
	l=k//(n-1)
	r=k%(n-1)
	if r==0:
		r=-1
	print(l*n+r)