#include <bits/stdc++.h>
bool isvowel(char s) {
  if (s == 'a' || s == 'A' || s == 'e' || s == 'E' || s == 'i' || s == 'I' ||
      s == 'o' || s == 'O' || s == 'u' || s == 'U')
    return true;
  else
    return false;
}
long long fact(long long n) {
  long long mul = 1;
  for (long long i = 1; i <= n; i++) mul = mul * i;
  return mul;
}
long long gcd(long long a, long long b) {
  return b == 0 ? a : gcd(b % 1000000007, (a % b) % 1000000007);
}
using namespace std;
const long long inf = 1e18;
int main() {
  int t, n, k;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    long long o = n;
    long long r = k % (n - 1);
    n--;
    long long c = k / n;
    long long ans = (c * o) + r;
    if (ans % o == 0) {
      cout << ans - 1 << "\n";
    } else
      cout << ans << "\n";
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
bool isvowel(char s) {
  if (s == 'a' || s == 'A' || s == 'e' || s == 'E' || s == 'i' || s == 'I' ||
      s == 'o' || s == 'O' || s == 'u' || s == 'U')
    return true;
  else
    return false;
}
long long fact(long long n) {
  long long mul = 1;
  for (long long i = 1; i <= n; i++) mul = mul * i;
  return mul;
}
long long gcd(long long a, long long b) {
  return b == 0 ? a : gcd(b % 1000000007, (a % b) % 1000000007);
}
using namespace std;
const long long inf = 1e18;
int main() {
  int t, n, k;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    long long o = n;
    long long r = k % (n - 1);
    n--;
    long long c = k / n;
    long long ans = (c * o) + r;
    if (ans % o == 0) {
      cout << ans - 1 << "\n";
    } else
      cout << ans << "\n";
  }
  return 0;
}

```