We have a point A with coordinate x = n on OX-axis. We'd like to find an integer point B (also on OX-axis), such that the absolute difference between the distance from O to B and the distance from A to B is equal to k.

<image> The description of the first test case.

Since sometimes it's impossible to find such point B, we can, in one step, increase or decrease the coordinate of A by 1. What is the minimum number of steps we should do to make such point B exist?

Input

The first line contains one integer t (1 ≤ t ≤ 6000) — the number of test cases.

The only line of each test case contains two integers n and k (0 ≤ n, k ≤ 10^6) — the initial position of point A and desirable absolute difference.

Output

For each test case, print the minimum number of steps to make point B exist.

Example

Input


6
4 0
5 8
0 1000000
0 0
1 0
1000000 1000000


Output


0
3
1000000
0
1
0

Note

In the first test case (picture above), if we set the coordinate of B as 2 then the absolute difference will be equal to |(2 - 0) - (4 - 2)| = 0 and we don't have to move A. So the answer is 0.

In the second test case, we can increase the coordinate of A by 3 and set the coordinate of B as 0 or 8. The absolute difference will be equal to |8 - 0| = 8, so the answer is 3.

<image>
#include <bits/stdc++.h>
using namespace std;
int t = 1000001;
class myData {
 public:
  int t;
  int x;
  int y;
  int d;
  myData(int t, int x, int y, int d) : t(t), x(x), y(y), d(d) {}
  bool operator<(const myData &a) const { return (this->t < a.t); }
};
long long exponentMod(long long A, long long B, long long C) {
  if (A == 0) return 0;
  if (B == 0) return 1;
  long long y;
  if (B % 2 == 0) {
    y = exponentMod(A, B / 2, C);
    y = (y * y) % C;
  } else {
    y = A % C;
    y = (y * exponentMod(A, B - 1, C) % C) % C;
  }
  return (long long)((y + C) % C);
}
pair<int, int> factorize(long long n) {
  int ans = 1;
  int c = 0;
  for (long long i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      if (i != 2) ans *= i, c++;
      n /= i;
    }
  }
  if (n != 1) {
    if (n != 2) ans *= n, c++;
  }
  return {ans, c};
}
map<long long, long long> bit;
int N1 = 2e5;
void update(long long i) {
  for (; i <= N1; i += i & (-i)) bit[i]++;
}
long long get(long long i) {
  long long ans = 0;
  for (; i > 0; i -= i & (-i)) ans += bit[i];
  return ans;
}
int now;
bool sortByVal(const myData &a, const myData &b) { return (a.t < b.t); }
long long ans1 = 0;
int spf[1000003];
long long calc[1000003 + 1];
long long nCk(long long n, long long k, long long mod) {
  return ((((calc[n] % mod) * exponentMod(calc[k], mod - 2, mod)) % mod) *
          exponentMod(calc[n - k], mod - 2, mod)) %
         mod;
}
void sieve() {
  spf[1] = 1;
  for (int i = 2; i < 1000003; i++) spf[i] = i;
  for (int i = 4; i < 1000003; i += 2) spf[i] = 2;
  for (int i = 3; i * i < 1000003; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j < 1000003; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
}
set<int> getFactorization(int x) {
  set<int> ret;
  while (x != 1) {
    ret.insert(spf[x]);
    x = x / spf[x];
  }
  return ret;
}
bool prime[1000003 + 1];
void sieve2() {
  memset(prime, true, sizeof(prime));
  for (int p = 2; p * p <= 1000003; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= 1000003; i += p) prime[i] = false;
    }
  }
}
int MEX(int a[], int n) {
  set<int> s;
  for (int i = 0; i < n; i++) {
    s.insert(a[i]);
  }
  int c = 0;
  for (auto i = s.begin(); i != s.end(); i++) {
    if (*i == c) {
      c++;
    } else
      break;
  }
  return c;
}
int smallestDivisor(int n) {
  if (n % 2 == 0) return 2;
  for (int i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}
const int M = 5050;
int a[M], dp[M][M];
int sum[500001];
int visited[500001];
vector<int> v[500001];
int dfs(int u, int p[], vector<int> v[]) {
  visited[u] = 1;
  int calc = p[u - 1];
  for (int i = 0; i < v[u].size(); i++) {
    if (!visited[v[u][i]]) {
      calc += dfs(v[u][i], p, v);
    }
  }
  cout << u << " " << calc << endl;
  return sum[u] = calc;
}
bool check(int u, int h[], int m, int s, vector<int> v[], int p[]) {
  visited[u] = 1;
  cout << u << " " << h[u - 1] << " " << m << " " << s << " " << p[u - 1]
       << endl;
  if (m == 0) {
    if (h[u - 1] != s && (m + s) != sum[u]) return false;
  } else {
    int d1 = m - s;
    int d2 = m + s;
    if ((m + s) % 2 == 0) {
      if (h[u - 1] < -d2 || h[u - 1] > d1 || h[u - 1] % 2 != 0 ||
          (m + s) != sum[u]) {
        return false;
      }
    } else {
      if (h[u - 1] < -d2 || h[u - 1] > d1 || h[u - 1] % 2 == 0 ||
          (m + s) != sum[u])
        return false;
    }
  }
  if (s >= p[u - 1]) {
    s -= p[u - 1];
  } else {
    m -= (p[u - 1] - s);
    s = 0;
  }
  for (int i = 0; i < v[u].size(); i++) {
    if (!visited[v[u][i]]) return check(v[u][i], h, m, s, v, p);
  }
  return true;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    if (n < k)
      cout << (k - n) << endl;
    else {
      if (k % 2 != n % 2)
        cout << 1 << endl;
      else
        cout << 0 << endl;
    }
  }
  return 0;
}
