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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class codeforces {
    static class pair {
        int x;
        int y;

        public pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static long sqrt(long x) {
        long s = 0, e = x, root = 0;
        while (s <= e) {
            long mid = (s + e) / 2;
            if (mid * mid == x)
                return mid;
            if (mid * mid < x) {
                root = mid;
                s = mid + 1;
            } else
                e = mid - 1;
        }
        return root;
    }

    public static long power(long a, long b) {
        if (a == 0 || b == 0)
            return 1L;
        long ans = power(a, b / 2);
        ans *= ans;
        if (b % 2 == 1)
            ans *= a;
        return ans;
    }

    public static boolean isSubsequence(String a, String b) {
        int m = a.length(), n = b.length(), i = 0, j = 0;
        while (i < m && j < n) {
            if (a.charAt(i) == b.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == m;
    }

    public static boolean isprime(long x) {
        if (x == 1)
            return false;
        if (x < 4)
            return true;
        int root = (int) Math.sqrt(x);
        for (int i = 2; i <= root; i++) {
            if (x % i == 0)
                return false;
        }
        return true;
    }

    public static long longmax(long a, long b) {
        return Math.max(a, b);
    }

    public static long longmin(long a, long b) {
        return Math.min(a, b);
    }

    public static int intmax(int a, int b) {
        return Math.max(a, b);
    }

    public static long intmin(int a, int b) {
        return Math.min(a, b);
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder str = new StringBuilder();
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine());
        String[] lol;
        while (t-- > 0) {
            // int n=Integer.parseInt(br.readLine());
            lol = br.readLine().split(" ");
            // int c=0;
            int n = Integer.parseInt(lol[0]), k = Integer.parseInt(lol[1]);
            if(n>k)
                str.append(k);
            
            else
                if(n==k)
                str.append(k+1);
            else{
                n--;
                if(k%n==0){
                    str.append(k/n-1+k);
                }
                else{
                    str.append(k+(k/n));
                }
            }
            str.append("\n");
        }
        out.print(str);
        out.close();
    }
}