#include <bits/stdc++.h>
using namespace std;
void build(long long v, long long tl, long long tr, long long st[],
           long long lz[], bool f[], long long a[]) {
  if (tl == tr) {
    st[v] = a[tl];
    lz[v] = 0LL;
    f[v] = false;
    return;
  }
  build((v << 1), tl, ((tl + tr) >> 1), st, lz, f, a);
  build((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, st, lz, f, a);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  lz[v] = 0LL;
  f[v] = false;
  return;
}
void push(long long v, long long tl, long long tr, long long st[],
          long long lz[], bool f[]) {
  if (f[v]) {
    st[(v << 1)] = lz[(v << 1)] = st[(v << 1) | 1] = lz[(v << 1) | 1] = 0LL;
    f[(v << 1)] = f[(v << 1) | 1] = true;
    f[v] = false;
  }
  st[(v << 1)] += lz[v] * (((tl + tr) >> 1) - tl + 1);
  lz[(v << 1)] += lz[v];
  st[(v << 1) | 1] += lz[v] * (tr - ((tl + tr) >> 1));
  lz[(v << 1) | 1] += lz[v];
  lz[v] = 0LL;
  return;
}
void update(long long v, long long tl, long long tr, long long l, long long r,
            long long val, bool set, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return;
  }
  if (l == tl && tr == r) {
    if (set) {
      st[v] = lz[v] = 0LL;
      f[v] = true;
    }
    st[v] += val * (tr - tl + 1);
    lz[v] += val;
    return;
  }
  push(v, tl, tr, st, lz, f);
  update((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), val, set,
         st, lz, f);
  update((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 1),
         r, val, set, st, lz, f);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  return;
}
long long query(long long v, long long tl, long long tr, long long l,
                long long r, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return 0LL;
  }
  if (l == tl && tr == r) {
    return st[v];
  }
  push(v, tl, tr, st, lz, f);
  return query((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), st,
               lz, f) +
         query((v << 1) | 1, ((tl + tr) >> 1) + 1, tr,
               max(l, ((tl + tr) >> 1) + 1), r, st, lz, f);
}
void build(int v, int tl, int tr, int a[], long long st[]) {
  if (tl == tr) {
    st[v] = a[tl];
    return;
  }
  int tm = ((tl + tr) / 2);
  build(2 * v, tl, tm, a, st);
  build(2 * v + 1, tm + 1, tr, a, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
void update(int v, int tl, int tr, int pos, int val, long long st[]) {
  if (tl == tr && tl == pos) {
    st[v] = val;
    return;
  }
  if (tl > pos || tr < pos) {
    return;
  }
  int tm = ((tl + tr) / 2);
  update(2 * v, tl, tm, pos, val, st);
  update(2 * v + 1, tm + 1, tr, pos, val, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
long long query(int v, int tl, int tr, int l, int r, long long st[]) {
  if (tl == l && tr == r) {
    return st[v];
  }
  if (l > r) {
    return 0LL;
  }
  int tm = ((tl + tr) / 2);
  return query(v * 2, tl, tm, l, std::min(tm, r), st) +
         query(v * 2 + 1, tm + 1, tr, std::max(tm + 1, l), r, st);
}
long long fn(long long x, long long rn[]) {
  if (x == rn[x])
    return x;
  else
    return rn[x] = fn(rn[x], rn);
}
bool un(long long x, long long y, long long rn[], long long sz[]) {
  x = fn(x, rn);
  y = fn(y, rn);
  if (x == y) return false;
  if (sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  rn[y] = x;
  return true;
}
bool compare(const pair<long long, long long> &a,
             const pair<long long, long long> &b) {
  return a.second < b.second;
}
pair<int, int> mostFrequent(long long arr[], long long n) {
  unordered_map<long long, long long> hash;
  for (long long i = 0; i < n; i++) hash[arr[i]]++;
  long long max_count = 0, res = -1;
  for (auto i : hash) {
    if (max_count < i.second) {
      res = i.first;
      max_count = i.second;
    }
  }
  pair<long long, long long> temp;
  temp.first = res;
  temp.second = max_count;
  return temp;
}
long long div(long long n) {
  if (n % 2 == 0) return 2;
  for (long long i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
bool sec(const pair<long long, long long> &a,
         const pair<long long, long long> &b) {
  return (a.first > b.first);
}
bool sec1(const pair<long long, long long> &a,
          const pair<long long, long long> &b) {
  return (a.second > b.second);
}
long long msum(long long a[], long long size) {
  long long max_so_far = a[0];
  long long curr_max = a[0];
  for (long long i = 0; i < size; i++) {
    curr_max = max(a[i], curr_max + a[i]);
    max_so_far = max(max_so_far, curr_max);
  }
  return max_so_far;
}
long long dist(tuple<long long, long long, long long> a,
               tuple<long long, long long, long long> b) {
  return ((get<0>(a) - get<0>(b)) * (get<0>(a) - get<0>(b)) +
          (get<1>(a) - get<1>(b)) * (get<1>(a) - get<1>(b)) +
          (get<2>(a) - get<2>(b)) * (get<2>(a) - get<2>(b)));
}
bool inv(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second > b.second);
}
long long ph(long long n) {
  long long res = 0;
  for (long long i = n; i >= 1; i--) {
    if ((i & (i - 1)) == 0) {
      res = i;
      break;
    }
  }
  return res;
}
long long M = 1000000007;
long long power(long long x, long long y, long long m) {
  if (y == 0) return 1;
  long long p = power(x, y / 2, m) % m;
  p = (p * p) % m;
  return (y % 2 == 0) ? p : (x * p) % m;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long a, b;
    cin >> a >> b;
    if (a == b) {
      cout << 0 << "\n";
      continue;
    }
    if (a < b) {
      if (a % 2 != b % 2) {
        cout << 1 << "\n";
      } else {
        cout << 2 << "\n";
      }
    } else if (a > b) {
      if (a % 2 == b % 2) {
        cout << 1 << "\n";
      } else {
        cout << 2 << "\n";
      }
    }
  }
}

### Prompt

Develop a solution in CPP to the problem described below:

You are given two positive integers a and b.

In one move, you can change a in the following way:

  * Choose any positive odd integer x (x > 0) and replace a with a+x; 
  * choose any positive even integer y (y > 0) and replace a with a-y. 



You can perform as many such operations as you want. You can choose the same numbers x and y in different moves.

Your task is to find the minimum number of moves required to obtain b from a. It is guaranteed that you can always obtain b from a.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Then t test cases follow. Each test case is given as two space-separated integers a and b (1 ≤ a, b ≤ 10^9).

Output

For each test case, print the answer — the minimum number of moves required to obtain b from a if you can perform any number of moves described in the problem statement. It is guaranteed that you can always obtain b from a.

Example

Input


5
2 3
10 10
2 4
7 4
9 3


Output


1
0
2
2
1

Note

In the first test case, you can just add 1.

In the second test case, you don't need to do anything.

In the third test case, you can add 1 two times.

In the fourth test case, you can subtract 4 and add 1.

In the fifth test case, you can just subtract 6.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void build(long long v, long long tl, long long tr, long long st[],
           long long lz[], bool f[], long long a[]) {
  if (tl == tr) {
    st[v] = a[tl];
    lz[v] = 0LL;
    f[v] = false;
    return;
  }
  build((v << 1), tl, ((tl + tr) >> 1), st, lz, f, a);
  build((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, st, lz, f, a);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  lz[v] = 0LL;
  f[v] = false;
  return;
}
void push(long long v, long long tl, long long tr, long long st[],
          long long lz[], bool f[]) {
  if (f[v]) {
    st[(v << 1)] = lz[(v << 1)] = st[(v << 1) | 1] = lz[(v << 1) | 1] = 0LL;
    f[(v << 1)] = f[(v << 1) | 1] = true;
    f[v] = false;
  }
  st[(v << 1)] += lz[v] * (((tl + tr) >> 1) - tl + 1);
  lz[(v << 1)] += lz[v];
  st[(v << 1) | 1] += lz[v] * (tr - ((tl + tr) >> 1));
  lz[(v << 1) | 1] += lz[v];
  lz[v] = 0LL;
  return;
}
void update(long long v, long long tl, long long tr, long long l, long long r,
            long long val, bool set, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return;
  }
  if (l == tl && tr == r) {
    if (set) {
      st[v] = lz[v] = 0LL;
      f[v] = true;
    }
    st[v] += val * (tr - tl + 1);
    lz[v] += val;
    return;
  }
  push(v, tl, tr, st, lz, f);
  update((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), val, set,
         st, lz, f);
  update((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 1),
         r, val, set, st, lz, f);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  return;
}
long long query(long long v, long long tl, long long tr, long long l,
                long long r, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return 0LL;
  }
  if (l == tl && tr == r) {
    return st[v];
  }
  push(v, tl, tr, st, lz, f);
  return query((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), st,
               lz, f) +
         query((v << 1) | 1, ((tl + tr) >> 1) + 1, tr,
               max(l, ((tl + tr) >> 1) + 1), r, st, lz, f);
}
void build(int v, int tl, int tr, int a[], long long st[]) {
  if (tl == tr) {
    st[v] = a[tl];
    return;
  }
  int tm = ((tl + tr) / 2);
  build(2 * v, tl, tm, a, st);
  build(2 * v + 1, tm + 1, tr, a, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
void update(int v, int tl, int tr, int pos, int val, long long st[]) {
  if (tl == tr && tl == pos) {
    st[v] = val;
    return;
  }
  if (tl > pos || tr < pos) {
    return;
  }
  int tm = ((tl + tr) / 2);
  update(2 * v, tl, tm, pos, val, st);
  update(2 * v + 1, tm + 1, tr, pos, val, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
long long query(int v, int tl, int tr, int l, int r, long long st[]) {
  if (tl == l && tr == r) {
    return st[v];
  }
  if (l > r) {
    return 0LL;
  }
  int tm = ((tl + tr) / 2);
  return query(v * 2, tl, tm, l, std::min(tm, r), st) +
         query(v * 2 + 1, tm + 1, tr, std::max(tm + 1, l), r, st);
}
long long fn(long long x, long long rn[]) {
  if (x == rn[x])
    return x;
  else
    return rn[x] = fn(rn[x], rn);
}
bool un(long long x, long long y, long long rn[], long long sz[]) {
  x = fn(x, rn);
  y = fn(y, rn);
  if (x == y) return false;
  if (sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  rn[y] = x;
  return true;
}
bool compare(const pair<long long, long long> &a,
             const pair<long long, long long> &b) {
  return a.second < b.second;
}
pair<int, int> mostFrequent(long long arr[], long long n) {
  unordered_map<long long, long long> hash;
  for (long long i = 0; i < n; i++) hash[arr[i]]++;
  long long max_count = 0, res = -1;
  for (auto i : hash) {
    if (max_count < i.second) {
      res = i.first;
      max_count = i.second;
    }
  }
  pair<long long, long long> temp;
  temp.first = res;
  temp.second = max_count;
  return temp;
}
long long div(long long n) {
  if (n % 2 == 0) return 2;
  for (long long i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
bool sec(const pair<long long, long long> &a,
         const pair<long long, long long> &b) {
  return (a.first > b.first);
}
bool sec1(const pair<long long, long long> &a,
          const pair<long long, long long> &b) {
  return (a.second > b.second);
}
long long msum(long long a[], long long size) {
  long long max_so_far = a[0];
  long long curr_max = a[0];
  for (long long i = 0; i < size; i++) {
    curr_max = max(a[i], curr_max + a[i]);
    max_so_far = max(max_so_far, curr_max);
  }
  return max_so_far;
}
long long dist(tuple<long long, long long, long long> a,
               tuple<long long, long long, long long> b) {
  return ((get<0>(a) - get<0>(b)) * (get<0>(a) - get<0>(b)) +
          (get<1>(a) - get<1>(b)) * (get<1>(a) - get<1>(b)) +
          (get<2>(a) - get<2>(b)) * (get<2>(a) - get<2>(b)));
}
bool inv(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second > b.second);
}
long long ph(long long n) {
  long long res = 0;
  for (long long i = n; i >= 1; i--) {
    if ((i & (i - 1)) == 0) {
      res = i;
      break;
    }
  }
  return res;
}
long long M = 1000000007;
long long power(long long x, long long y, long long m) {
  if (y == 0) return 1;
  long long p = power(x, y / 2, m) % m;
  p = (p * p) % m;
  return (y % 2 == 0) ? p : (x * p) % m;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long a, b;
    cin >> a >> b;
    if (a == b) {
      cout << 0 << "\n";
      continue;
    }
    if (a < b) {
      if (a % 2 != b % 2) {
        cout << 1 << "\n";
      } else {
        cout << 2 << "\n";
      }
    } else if (a > b) {
      if (a % 2 == b % 2) {
        cout << 1 << "\n";
      } else {
        cout << 2 << "\n";
      }
    }
  }
}

```