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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main
{
	public static void main(String[] args) throws IOException
	{
		int t=ini();
		while (t-->0)
		{
			int n=ini();//n的倍数不要
			int k=ini();//第k个数
			
			long sum=k;
			long shan=sum/n;//要删除这些数
			long ans=sum-shan;//实际拿到了第几个数
			while (ans<k)
			{
				sum=sum+(k-ans);
				shan=sum/n;
				ans=sum-shan;
			}
			out.println(sum);
			out.flush();
		}
	}
	
	static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static int ini() throws IOException
	{
		in.nextToken();
		return (int)in.nval;
	}
	static double ind() throws IOException
	{
		in.nextToken();
		return in.nval;
	}
	static String ins() throws IOException
	{
		in.nextToken();
		return in.sval;
	}
	
}