#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
struct mint {
  long long x;
  mint() : x(0) {}
  mint(long long x) : x((x % mod + mod) % mod) {}
  mint& fix() {
    x = (x % mod + mod) % mod;
    return *this;
  }
  mint operator-() const { return mint(0) - *this; }
  mint& operator+=(const mint& a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint& a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint& a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint& a) const { return mint(*this) += a; }
  mint operator-(const mint& a) const { return mint(*this) -= a; }
  mint operator*(const mint& a) const { return mint(*this) *= a; }
  bool operator<(const mint& a) const { return x < a.x; }
  bool operator==(const mint& a) const { return x == a.x; }
};
template <typename T>
void show(vector<T> v) {
  for (auto it : v) {
    cout << it << " ";
  }
  cout << "\n";
}
void solve() {
  int r, l;
  std::cin >> l >> r;
  if (l == r) {
    std::cout << 0 << "\n";
    return;
  }
  int left = (r + 1) / 2;
  if (left < l) left = l;
  int remain = r % left;
  int rr = (r - 1) % left;
  std::cout << std::max(remain, rr) << "\n";
}
int main() {
  int t = 1;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
const long long mod = 1000000007;
struct mint {
  long long x;
  mint() : x(0) {}
  mint(long long x) : x((x % mod + mod) % mod) {}
  mint& fix() {
    x = (x % mod + mod) % mod;
    return *this;
  }
  mint operator-() const { return mint(0) - *this; }
  mint& operator+=(const mint& a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint& a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint& a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint& a) const { return mint(*this) += a; }
  mint operator-(const mint& a) const { return mint(*this) -= a; }
  mint operator*(const mint& a) const { return mint(*this) *= a; }
  bool operator<(const mint& a) const { return x < a.x; }
  bool operator==(const mint& a) const { return x == a.x; }
};
template <typename T>
void show(vector<T> v) {
  for (auto it : v) {
    cout << it << " ";
  }
  cout << "\n";
}
void solve() {
  int r, l;
  std::cin >> l >> r;
  if (l == r) {
    std::cout << 0 << "\n";
    return;
  }
  int left = (r + 1) / 2;
  if (left < l) left = l;
  int remain = r % left;
  int rr = (r - 1) % left;
  std::cout << std::max(remain, rr) << "\n";
}
int main() {
  int t = 1;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

```