#include <bits/stdc++.h>
using namespace std;
vector<int> vec{};
int numof(string sing, char x) {
  map<char, int> nuof;
  string a = sing;
  for (char c : a) {
    nuof[c]++;
  }
  return nuof[x];
}
int main() {
  ios_base::sync_with_stdio(0);
  long long int a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u,
      v, w, x, y, z, count, maxx, minn;
  a = b = c = d = e = f = g = h = i = j = k = l = m = n = o = p = q = r = s =
      t = u = v = w = x = y = z = count = 0;
  string st;
  char ch;
  cin >> t;
  while (t--) {
    cin >> l >> r;
    if ((r % 2 == 0 ? r : r + 1) / 2 >= l) {
      cout << (r % 2 == 0 ? r : r + 1) / 2 - 1 << "\n";
    } else {
      cout << r - l << "\n";
    }
  }
}

### Prompt

Please create a solution in Cpp to the following problem:

You are given two integers l and r, l≤ r. Find the largest possible value of a mod b over all pairs (a, b) of integers for which r≥ a ≥ b ≥ l.

As a reminder, a mod b is a remainder we get when dividing a by b. For example, 26 mod 8 = 2.

Input

Each test contains multiple test cases.

The first line contains one positive integer t (1≤ t≤ 10^4), denoting the number of test cases. Description of the test cases follows.

The only line of each test case contains two integers l, r (1≤ l ≤ r ≤ 10^9).

Output

For every test case, output the largest possible value of a mod b over all pairs (a, b) of integers for which r≥ a ≥ b ≥ l.

Example

Input


4
1 1
999999999 1000000000
8 26
1 999999999


Output


0
1
12
499999999

Note

In the first test case, the only allowed pair is (a, b) = (1, 1), for which a mod b = 1 mod 1 = 0.

In the second test case, the optimal choice is pair (a, b) = (1000000000, 999999999), for which a mod b = 1.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> vec{};
int numof(string sing, char x) {
  map<char, int> nuof;
  string a = sing;
  for (char c : a) {
    nuof[c]++;
  }
  return nuof[x];
}
int main() {
  ios_base::sync_with_stdio(0);
  long long int a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u,
      v, w, x, y, z, count, maxx, minn;
  a = b = c = d = e = f = g = h = i = j = k = l = m = n = o = p = q = r = s =
      t = u = v = w = x = y = z = count = 0;
  string st;
  char ch;
  cin >> t;
  while (t--) {
    cin >> l >> r;
    if ((r % 2 == 0 ? r : r + 1) / 2 >= l) {
      cout << (r % 2 == 0 ? r : r + 1) / 2 - 1 << "\n";
    } else {
      cout << r - l << "\n";
    }
  }
}

```