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.IOException;
import java.io.PrintWriter;
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.InputStreamReader;
// import java.util.ArrayDeque;
// import java.util.List;
// import java.util.ArrayList;
// import java.util.Arrays;
// import java.util.Collections;
// import java.util.Comparator;
// import java.util.Map;
// import java.util.HashMap;
// import java.util.Set;
// import java.util.HashSet;
// import java.util.NoSuchElementException;
// import java.util.PriorityQueue;
// import java.util.Queue;
// import java.util.Random;
// import java.util.Scanner;
// import java.util.TreeMap;
// import java.util.TreeSet;

public class Solution {
  public void solve(FastReader in, PrintWriter pw) {
    int t = in.nextInt();

    while (t-- > 0) {
      int n = in.nextInt();
      int k = in.nextInt();
      int need = (k - 1) / (n - 1);
      pw.println(k + need);
    }
  }

  public static void main(String[] args) throws IOException {
    FastReader in = new FastReader();
    PrintWriter pw = new PrintWriter(System.out);
    new Solution().solve(in, pw);
    pw.flush();
    pw.close();
  }
}

class ArrayUtils {
  public static int[] readIntArray(int size, FastReader in) {
    int[] arr = new int[size];
    for (int i = 0; i < size; i++) arr[i] = in.nextInt();
    return arr;
  }
}

class Numbers {
  public static int MOD = 10;
  public static int modPow(int a, int b) {
    if (b == 0) return 1;

    return ((b & 1) > 0 ? a : 1) * modPow((a * a) % MOD, b >>> 1) % MOD;
  }
}

class FastReader
{
  BufferedReader br;
  StringTokenizer st;

  public FastReader()
  {
    br=new BufferedReader(new InputStreamReader(System.in));
  }

  public String next()
  {
    if(st==null || !st.hasMoreElements())
    {
      try {
        st=new StringTokenizer(br.readLine());
      } catch(Exception e) {
        throw new RuntimeException(e);
      }
    }
    return st.nextToken();
  }

  public int nextInt()
  {
    return Integer.parseInt(next());
  }

  public long nextLong()
  {
    return Long.parseLong(next());
  }
}