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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class ABC197 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>q,w;
	static HashSet<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>h,tmp;
	static boolean[]vis;
	static int[]a,b,c,d,mx,mn,nxt;
	static long[]l,ti;
	static char[][]mp;
	static int px,py,tx,ty;
	static String s,t;
	static long oo=(long)1e18,dp[][];
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
		//B();
	    //C();
		//D();
		//E();
		//F();
		x();
		out.close();
	}
	  private static void x() throws IOException {
		   int t=ni();
		   while(t-->0) {
			   int n=ni(),k=ni();
			   int tt=k/(n-1);
			   if(k>=n)
				   out.println(k+k/(n-1)+(k%(n-1)==0?-1:0));
			   else
				   out.println(k);
		   }
	   }
	  private static void A() throws IOException {
		    String s=ns();
		    out.println(s.substring(1)+s.charAt(0));
	   }
		static void B() throws IOException {
			int h=ni(),w=ni(),x=ni()-1,y=ni()-1;
			char[][]mp=new char[h][w];
			for(int i=0;i<h;i++) {
				mp[i]=ns().toCharArray();
			}
			int num=0;
			if(mp[x][y]=='.')num++;
			for(int i=x-1;i>=0;i--) {
				if(mp[i][y]=='#')break;
				num++;
			}
			for(int i=y-1;i>=0;i--) {
				if(mp[x][i]=='#')break;
				num++;
			}
			for(int i=x+1;i<h;i++) {
				if(mp[i][y]=='#')break;
				num++;
			}
			for(int i=y+1;i<w;i++) {
				if(mp[x][i]=='#')break;
				num++;
			}
			out.println(num);
			}
		static void C() throws IOException{
			int n=ni();
			a=nai(n);
			int trgt=1<<n;
			int min=Integer.MAX_VALUE;
			for(int i=0;i<trgt;i++) {
				int cur=0;
				ArrayList<Integer>vals=new ArrayList<Integer>();
				int prv=i&1;cur=a[0];
				for(int j=1;j<n;j++) {
					int c=(i>>j)&1;
					if(c==prv) {
						cur|=a[j];
					}else {
						vals.add(cur);
						prv=c;
						cur=a[j];
					}
				}
				vals.add(cur);
				int num=vals.get(0);
				for(int j=1;j<vals.size();j++) {
					num^=vals.get(j);
				}
				min=Math.min(min, num);
			}
			out.println(min);
		}

		public static long powR(long a,long b) {
			if(b==0)return 1;
			long sq=powR(a,b/2);
			sq*=sq*1l;
			if(b%2==1) {
				sq*=b;
			}
			return sq;
		}
	static void D() throws IOException {
		int n=ni();
		double x0=nd(),y0=nd();
		double xn=nd(),yn=nd();
		double xm=(x0+xn)/2.0;
		double ym=(y0+yn)/2.0;
		double dsq=(xm-x0)*(xm-x0)+(ym-y0)*(ym-y0);
		//out.println(dsq);
		double sin=Math.sin(Math.PI/n);
		double cos=Math.cos(Math.PI/n);
		//out.println(sin);
		double sum=x0*x0+y0*y0-xm*xm-ym*ym+dsq-4*dsq*sin*sin;
		sum/=(2.0*(x0-xm));
		double dist=4*dsq*cos*cos;
		sum-=yn;
		double a=2;
		double b=2*xn+2*sum;
		double c=xn*xn+sum*sum-dist;
		double x11=(b+Math.sqrt(b*b-4*a*c))/2.0*a;
		double x12=(b-Math.sqrt(b*b-4*a*c))/2.0*a;
		out.println(x11+" "+x12);
	}


	
	static long gcd (long a,long b) {
	    return b==0?a:gcd (b, a % b);
	}
	
	static void E() throws IOException {
		int n=ni();
		//int[][]a=new int[n][2];
		mx=new int[n+1];
		mn=new int[n+1];
		Arrays.fill(mx, Integer.MIN_VALUE);
		Arrays.fill(mn, Integer.MAX_VALUE);
		for(int i=0;i<n;i++) {
			int x=ni();
			int c=ni();
			mx[c]=Math.max(mx[c], x);
			mn[c]=Math.min(mn[c], x);
		}
		nxt=new int[n+1];
		mx[0]=mn[0]=0;
		int cur=0;
		while(cur<=n) {
			while(cur<=n&&mn[cur]==Integer.MAX_VALUE)cur++;
			if(cur>n)break;
			int next=cur+1;
			while(next<=n&&mn[next]==Integer.MAX_VALUE)next++;
			nxt[cur]=next;
			cur=next;
		}
		dp=new long[2][n+1];
		Arrays.fill(dp[0], -1);
		Arrays.fill(dp[1], -1);
		out.println(dp(0,0));
		
	}

	private static long dp(int h, int c) {
		//if(nxt[c]>nxt.length)return c;
		if(dp[h][c]!=-1)return dp[h][c];
		int cur=h==0?mx[c]:mn[c];
		if(nxt[c]>=nxt.length)return dp[h][c]=Math.abs(cur);
		long dist=Math.abs(mx[nxt[c]]-mn[nxt[c]]);
		long mnmx=(Math.abs(cur-mn[nxt[c]]))+dist+dp(0,nxt[c]);
		long mxmn=(Math.abs(cur-mx[nxt[c]]))+dist+dp(1,nxt[c]);
		return dp[h][c]=Math.min(mxmn, mnmx);
	}
	static boolean valid(int i,int j) {
		return i>=0&&i<mp.length&&j>=0&&j<mp[0].length&&mp[i][j]!='#';
	}
	static void F() throws IOException {
		
	}
	static class FenwickTree{
		int n;int[]ft;
		FenwickTree(int n){this.n=n;ft=new int[n+1];}
		int rsq(int b) {
			int sum =0;
			while(b>0) {sum^=ft[b];b-= b & -b;}
			return sum;
		}
		int rsq(int a,int b) {
			return rsq(b)^rsq(a-1);
		}
		void point_update(int k,int val){
			while(k<=n) {ft[k]^=val;k+= k & -k;}
		}

		int point_query(int idx)	// c * O(log n), c < 1
		{
			int sum = ft[idx];
			if(idx > 0)
			{
				int z = idx ^ (idx & -idx);
				--idx;
				while(idx != z)
				{
					sum ^= ft[idx];
					idx ^= idx & -idx;
				}
			}
			return sum;
		}
		
	}

	private static void disp(int[] revl) {
		for(int i=0;i<revl.length;i++) {
			out.print(revl[i]+" ");
		}
		out.println();
	}
	static class Pair implements Comparable<Pair>{
		int a,b;
		Pair(int a,int b){
			this.a=a;
			this.b=b;
		}
		@Override
		public int compareTo(Pair p) {
			return a-p.a;
		}
		public boolean equals(Pair p) {
			return a==p.a&&b==p.b;
		}
		public String toString() {
			return "("+a+" "+b+")";
		}
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}
	static void disp2(Pair []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}
	static class Edge {
		Point p;
		int val;
		Edge(Point a,int b){
			p=a;
			val=b;
		}
		
	}
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}