#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")
using namespace std;
using namespace std;
inline long long int addmod(long long int a, long long int b) {
  return (a % 1000000007 + b % 1000000007) % 1000000007;
}
inline long long int submod(long long int a, long long int b) {
  return (a % 1000000007 - b % 1000000007) % 1000000007;
}
inline long long int mulmod(long long int a, long long int b) {
  return ((a % 1000000007) * (b % 1000000007)) % 1000000007;
}
bool isPrime(int n) {
  if (n == 1) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
vector<int> factors(int n) {
  vector<int> fact;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      fact.push_back(i);
      if (i * i != n) {
        fact.push_back(n / i);
      }
    }
  }
  return fact;
}
long long int pw(long long int a, long long int b) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a);
    }
    b = b >> 1;
    a = (a * a);
  }
  return res;
}
long long int pwmod(long long int a, long long int b) {
  long long int res = 1;
  a = a % 1000000007;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % 1000000007;
    }
    b = b >> 1;
    a = (a * a) % 1000000007;
  }
  return res;
}
long long int modinv(long long int a) { return pwmod(a, 1000000007 - 2); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, k;
    cin >> n >> k;
    if (n == k)
      cout << (k + 1) << "\n";
    else if (n > k)
      cout << k << "\n";
    else {
      int val = k / (n - 1);
      val += k;
      if (k % (n - 1) == 0) val--;
      cout << val << "\n";
    }
  }
  return 0;
}

### Prompt

Develop a solution in CPP 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>
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")
using namespace std;
using namespace std;
inline long long int addmod(long long int a, long long int b) {
  return (a % 1000000007 + b % 1000000007) % 1000000007;
}
inline long long int submod(long long int a, long long int b) {
  return (a % 1000000007 - b % 1000000007) % 1000000007;
}
inline long long int mulmod(long long int a, long long int b) {
  return ((a % 1000000007) * (b % 1000000007)) % 1000000007;
}
bool isPrime(int n) {
  if (n == 1) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
vector<int> factors(int n) {
  vector<int> fact;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      fact.push_back(i);
      if (i * i != n) {
        fact.push_back(n / i);
      }
    }
  }
  return fact;
}
long long int pw(long long int a, long long int b) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a);
    }
    b = b >> 1;
    a = (a * a);
  }
  return res;
}
long long int pwmod(long long int a, long long int b) {
  long long int res = 1;
  a = a % 1000000007;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % 1000000007;
    }
    b = b >> 1;
    a = (a * a) % 1000000007;
  }
  return res;
}
long long int modinv(long long int a) { return pwmod(a, 1000000007 - 2); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, k;
    cin >> n >> k;
    if (n == k)
      cout << (k + 1) << "\n";
    else if (n > k)
      cout << k << "\n";
    else {
      int val = k / (n - 1);
      val += k;
      if (k % (n - 1) == 0) val--;
      cout << val << "\n";
    }
  }
  return 0;
}

```