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.DataInputStream;
import java.io.IOException;
import java.text.DecimalFormat;
import java.util.*;

public class CodeChef {

    public static void main(final String[] args) throws IOException {

        int t = console.nextInt();
        while (t-- > 0) {

            long N = console.nextLong();
            long K = console.nextLong();
            long count = K + K/(N-1);

            if (K % (N-1) == 0) System.out.println(count - 1);
            else System.out.println(count);
        }
    }
//    static class Pair {
//        int a;
//        int b;
//
//        public Pair(int a, int b) {
//            this.a = a;
//            this.b = b;
//        }
//
//    }

    private static final CodeChef.InputReader console = new CodeChef.InputReader();

    static final class InputReader {
        private final int BUFFER_SIZE = 1 << 24;

        private final DataInputStream in = new DataInputStream(System.in);
        private final byte[] buffer = new byte[BUFFER_SIZE];
        private final byte[] buf = new byte[BUFFER_SIZE];
        private int bufferPointer = 0, bytesRead = 0;

        private void fillBuffer() throws IOException {
            bytesRead = in.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) {
                buffer[0] = -1;
            }
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) {
                fillBuffer();
            }
            return buffer[bufferPointer++];
        }

        public String next() throws IOException {
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c < 33) {
                    break;
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public String nextLine() throws IOException {
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\r' || c == '\n') {
                    break;
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            return (int) nextLong();
        }

        public long nextLong() throws IOException {
            long ret = 0L, c = read();
            while (c < 33L) {
                c = read();
            }
            boolean neg = (c == 45L);
            if (neg) {
                c = read();
            }
            do {
                ret = (ret << 3) + (ret << 1) + c - 48L;
            } while ((c = read()) > 47 && c < 58);
            return (neg ? -ret : ret);
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public void close() throws IOException {
            in.close();
        }
    }
}