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.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 
import java.util.*; 
/**
 * :)
 **/
 
public class Main 
{ 
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
  public static long primeFactors(long n)
{
    long ans=1;
    if(n%2==0)
    ans*=2*1l;
    while (n%2 == 0)
    {
        n = n/2;
    }
    
    for (int i = 3; i*i<=n; i = i+2)
    {
        if(n%i==0)
        ans*=i*1l;
        while (n%i == 0)
        {
            n = n/i;
        }
    }
   
    if (n > 2)
        ans*=n*1l;
        return ans;
}

public static long gcd( long a, long b)
{
    if(b==0)
    return a;
    return gcd(b, a%b);
}
    public static void main(String[] args) 
    { 
        FastReader sc=new FastReader(); 
	 
	    int t=sc.nextInt();
	    	StringBuilder sb =new StringBuilder();
	    
	    while(t-->0)
	    {
	       
	     int n=sc.nextInt();
	     int k=sc.nextInt();
	     int ans=0;
	     int n1=k;
	     while(n1>=n)
	     {
	     int mul=(n1/n)*n;
	     int rem=n1-mul;
	     
	    int add=0;
	    add=mul/n;
	    ans+=add;
	    rem+=add;
	    n1=rem;
	   }
	   sb.append(k+ans);
	   sb.append("\n");
	    }
	    System.out.print(sb.toString());
    
	    //System.out.print(sb.toString());
		
	}
	public static void sort( long a[])
	{
	    ArrayList<Long> adj=new ArrayList<>();
	    for( int i=0;i<a.length;i++)
	    {
	        adj.add(a[i]);
	    }
	    Collections.sort(adj);
	    for( int i=0;i<a.length;i++)
	    {
	        a[i]=adj.get(i);
	    }
	}
	public static long find(int ind, long bit[])
    {
        long sum=0;
        while(ind>0)
        {
           long last_bit= (ind) & (-ind);
           sum+=bit[ind];
           ind-=last_bit;
           
        }
        return sum;
    }
    public static void update( long bit[], int ind, int val, int lim )
    {
        while(ind<=lim)
        {
            bit[ind]+=val;
            ind+=(ind)&(-ind);
        }
    }
}