#include <bits/stdc++.h>
using namespace std;
void vprint(vector<int>& v) {
  for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
  cout << endl;
}
void aprint(int* arr, int n) {
  for (int i = 0; i < n; i++) cout << arr[i] << ' ';
  cout << endl;
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2>& p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
int main() {
  long long int tc;
  cin >> tc;
  while (tc--) {
    long long int n, k;
    cin >> n >> k;
    long long int left = 1;
    long long int right = pow(10, 13);
    while (left <= right) {
      long long int mid = (left + right) / 2;
      long long int div = mid / n;
      long long int va = mid - div;
      if (va == k) {
        if (mid % n == 0)
          cout << mid - 1 << endl;
        else {
          cout << mid << endl;
        }
        break;
      } else if (va > k) {
        right = mid - 1;
      } else
        left = mid + 1;
    }
  }
}

### 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>
using namespace std;
void vprint(vector<int>& v) {
  for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
  cout << endl;
}
void aprint(int* arr, int n) {
  for (int i = 0; i < n; i++) cout << arr[i] << ' ';
  cout << endl;
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2>& p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
int main() {
  long long int tc;
  cin >> tc;
  while (tc--) {
    long long int n, k;
    cin >> n >> k;
    long long int left = 1;
    long long int right = pow(10, 13);
    while (left <= right) {
      long long int mid = (left + right) / 2;
      long long int div = mid / n;
      long long int va = mid - div;
      if (va == k) {
        if (mid % n == 0)
          cout << mid - 1 << endl;
        else {
          cout << mid << endl;
        }
        break;
      } else if (va > k) {
        right = mid - 1;
      } else
        left = mid + 1;
    }
  }
}

```