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.util.Scanner;

public class Main {
    public static void main(String[] args)
    {
        int t;
        int k_th=0;
        int rescount=0;
        Scanner c = new Scanner(System.in) ;
        t = c.nextInt();
        int[] arr =  new int[t*2];
        int[] res =  new int[t+1];
        //initialize the input array
        for (int i=0;i<t*2;i++)
        {
            arr[i]= c.nextInt();
        }
        //for every test number of divisibility
        for(int i =0;i<t*2;i+=2)
        {
            long last = 1999999999;
            long first = 1;
            long mid= (last+first)/2;
            long midpos=0;
            long lastpos=( last-last%arr[i] ) - ( (last- (last%arr[i])) /arr[i] )+(last%arr[i]);
            long firstpos=( first-first%arr[i] ) - ( (first- (first%arr[i])) /arr[i] )+(first%arr[i]);
            //in case k>n should start counting from k
            if (arr[i]<arr[i+1])
            {
                //check edges
                if (lastpos==arr[i+1])
                {
                    mid=last;
                }
                else if(firstpos==arr[i+1])
                 {
                     mid=first;
                 }
                else
                    {


               for (int f=0;mid<=last&&mid>=first;f++)
               {
                  

                midpos =  ( mid-mid%arr[i] ) - ( (mid- (mid%arr[i])) /arr[i] )+(mid%arr[i]);
                if (midpos<arr[i+1])
                {
                    first= mid ;
                    mid = (first+last)/2;

                }
                if (midpos>arr[i+1])
                {
                    last= mid ;
                    mid = (first+last)/2;

                }
                if (midpos==arr[i+1])
                {
                    break;
                }



               }
                    }
               if(mid%arr[i]==0){mid--;}
                res[rescount]=(int)mid;
                rescount++;

            }
            //in case k<n the the number is k
            if (arr[i]>arr[i+1])
            {
                res[rescount]=arr[i+1];
                rescount++;
            }
            //in case k=n the the number is k+1
            if (arr[i]==arr[i+1])
            {
                res[rescount]=arr[i+1]+1;
                rescount++;
            }


        }
        //output the result
        for (int i=0;i<t;i++)
        {
            System.out.println(res[i]);
        }

    }
}