#include <bits/stdc++.h>
using namespace std;
long long z;
long long to_dec(string s) {
  char rim[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
  long long decc[7] = {1, 5, 10, 50, 100, 500, 1000};
  long long res = 0;
  for (long long i = 0; i < s.size(); i++) {
    long long tdig;
    for (long long j = 0; j < 7; j++) {
      if (rim[j] == s[i]) tdig = decc[j];
    }
    if (i < (long long)s.size() - 1 &&
        (s[i] == 'I' && s[i + 1] == 'V' || s[i] == 'I' && s[i + 1] == 'X' ||
         s[i] == 'X' && s[i + 1] == 'L' || s[i] == 'X' && s[i + 1] == 'C' ||
         s[i] == 'C' && s[i + 1] == 'D' || s[i] == 'C' && s[i + 1] == 'M')) {
      tdig *= (-1);
    }
    res += tdig;
  }
  return res;
}
vector<long long> decomp(long long n) {
  vector<long long> res;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res.push_back(i);
      n /= i;
    }
  }
  if (n > 1) res.push_back(n);
  return res;
}
bool IsDigit(char a) {
  if (a <= '9' && a >= '0')
    return 1;
  else
    return 0;
}
bool IsLetter(char a) {
  if ((a <= 'z' && a >= 'a') || (a <= 'Z' && a >= 'A'))
    return 1;
  else
    return 0;
}
signed F(long long a) {
  z = 1;
  if (a == 0) return 1;
  for (long long i = 1; i <= a; i++) {
    z = z * i;
  }
  return z;
}
bool IsPrime(long long a) {
  if (a <= 0) return 0;
  if (a == 1) return 0;
  if (a == 2) return 1;
  for (long long i = 2; i * i <= a; i++) {
    if (a % i == 0) return 0;
  }
  return 1;
}
bool cmirt(long long n) {
  vector<long long> m;
  if (IsPrime(n)) return 0;
  long long l;
  m = decomp(n);
  long long sm1 = 0;
  z = n;
  while (z > 0) {
    sm1 += z % 10;
    z /= 10;
  }
  long long sm2 = 0;
  for (long long i = 0; i < m.size(); i++) {
    z = m[i];
    while (z > 0) {
      sm2 += z % 10;
      z /= 10;
    }
  }
  if (sm2 == sm1)
    return 1;
  else
    return 0;
}
vector<long long> srt(vector<long long>& v) {
  for (long long i = 0; i < v.size() - 1; i++) {
    for (long long j = i + 1; j < v.size(); j++) {
      if (v[i] > v[j]) swap(v[i], v[j]);
    }
  }
  return v;
}
long long kol_sosed(long long x, long long y, vector<string> v, char h,
                    long long n, long long m) {
  long long res;
  long long dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
  long long dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  for (long long i = 0; i < 8; i++) {
    long long nx = x + dx[i];
    long long ny = y + dy[i];
    if (nx < 0) nx += n;
    if (ny < 0) ny += m;
    nx = nx % n;
    ny = ny % m;
    res += (v[nx][ny] == h);
  }
  return res;
}
vector<long long> srtl(vector<long long> v, long long mx) {
  vector<long long> pockets(mx + 1);
  for (long long i = 0; i < (long long)v.size(); i++) {
    pockets[v[i]]++;
  }
  long long k = 0;
  for (long long i = 0; i < (long long)pockets.size(); i++) {
    while (pockets[i] > 0) {
      v[k] = i;
      pockets[i]--;
      k++;
    }
  }
  return v;
}
vector<long long> maxr(vector<long long> v, long long n) {
  long long mx = -1e18;
  vector<long long> maxr(n, -1e18);
  for (long long i = n - 1; i >= 0; i--) {
    mx = max(mx, v[i]);
    maxr[i] = mx;
  }
  return maxr;
}
vector<long long> maxl(vector<long long> v, long long n) {
  long long mx = -1e18;
  vector<long long> maxl(n, -1e18);
  for (long long i = 0; i < n; i++) {
    mx = max(mx, v[i]);
    maxl[i] = mx;
  }
  return maxl;
}
string in_chr(long long n) {
  string s = "";
  while (n > 0) {
    s += (char)(n % 10) + 48;
    n /= 10;
  }
  return s;
}
void solve() {
  long long a, b;
  cin >> a >> b;
  if (a < b) {
    z = a;
    a = b;
    b = z;
  }
  if ((a - b) % 2 == 1) {
    cout << -1 << endl;
    return;
  }
  if (a == b) {
    if (a == 0) {
      cout << 0 << endl;
    } else {
      cout << 1 << endl;
    }
  } else {
    cout << 2 << endl;
  }
}
signed main() {
  long long u;
  cin >> u;
  while (u--) {
    solve();
  }
}

### Prompt

Develop a solution in CPP to the problem described below:

<image>

William has two numbers a and b initially both equal to zero. William mastered performing three different operations with them quickly. Before performing each operation some positive integer k is picked, which is then used to perform one of the following operations: (note, that for each operation you can choose a new positive integer k)

  1. add number k to both a and b, or 
  2. add number k to a and subtract k from b, or 
  3. add number k to b and subtract k from a. 



Note that after performing operations, numbers a and b may become negative as well.

William wants to find out the minimal number of operations he would have to perform to make a equal to his favorite number c and b equal to his second favorite number d.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4). Description of the test cases follows.

The only line of each test case contains two integers c and d (0 ≤ c, d ≤ 10^9), which are William's favorite numbers and which he wants a and b to be transformed into.

Output

For each test case output a single number, which is the minimal number of operations which William would have to perform to make a equal to c and b equal to d, or -1 if it is impossible to achieve this using the described operations.

Example

Input


6
1 2
3 5
5 3
6 6
8 0
0 0


Output


-1
2
2
1
2
0

Note

Let us demonstrate one of the suboptimal ways of getting a pair (3, 5):

  * Using an operation of the first type with k=1, the current pair would be equal to (1, 1). 
  * Using an operation of the third type with k=8, the current pair would be equal to (-7, 9). 
  * Using an operation of the second type with k=7, the current pair would be equal to (0, 2). 
  * Using an operation of the first type with k=3, the current pair would be equal to (3, 5). 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long z;
long long to_dec(string s) {
  char rim[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
  long long decc[7] = {1, 5, 10, 50, 100, 500, 1000};
  long long res = 0;
  for (long long i = 0; i < s.size(); i++) {
    long long tdig;
    for (long long j = 0; j < 7; j++) {
      if (rim[j] == s[i]) tdig = decc[j];
    }
    if (i < (long long)s.size() - 1 &&
        (s[i] == 'I' && s[i + 1] == 'V' || s[i] == 'I' && s[i + 1] == 'X' ||
         s[i] == 'X' && s[i + 1] == 'L' || s[i] == 'X' && s[i + 1] == 'C' ||
         s[i] == 'C' && s[i + 1] == 'D' || s[i] == 'C' && s[i + 1] == 'M')) {
      tdig *= (-1);
    }
    res += tdig;
  }
  return res;
}
vector<long long> decomp(long long n) {
  vector<long long> res;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res.push_back(i);
      n /= i;
    }
  }
  if (n > 1) res.push_back(n);
  return res;
}
bool IsDigit(char a) {
  if (a <= '9' && a >= '0')
    return 1;
  else
    return 0;
}
bool IsLetter(char a) {
  if ((a <= 'z' && a >= 'a') || (a <= 'Z' && a >= 'A'))
    return 1;
  else
    return 0;
}
signed F(long long a) {
  z = 1;
  if (a == 0) return 1;
  for (long long i = 1; i <= a; i++) {
    z = z * i;
  }
  return z;
}
bool IsPrime(long long a) {
  if (a <= 0) return 0;
  if (a == 1) return 0;
  if (a == 2) return 1;
  for (long long i = 2; i * i <= a; i++) {
    if (a % i == 0) return 0;
  }
  return 1;
}
bool cmirt(long long n) {
  vector<long long> m;
  if (IsPrime(n)) return 0;
  long long l;
  m = decomp(n);
  long long sm1 = 0;
  z = n;
  while (z > 0) {
    sm1 += z % 10;
    z /= 10;
  }
  long long sm2 = 0;
  for (long long i = 0; i < m.size(); i++) {
    z = m[i];
    while (z > 0) {
      sm2 += z % 10;
      z /= 10;
    }
  }
  if (sm2 == sm1)
    return 1;
  else
    return 0;
}
vector<long long> srt(vector<long long>& v) {
  for (long long i = 0; i < v.size() - 1; i++) {
    for (long long j = i + 1; j < v.size(); j++) {
      if (v[i] > v[j]) swap(v[i], v[j]);
    }
  }
  return v;
}
long long kol_sosed(long long x, long long y, vector<string> v, char h,
                    long long n, long long m) {
  long long res;
  long long dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
  long long dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  for (long long i = 0; i < 8; i++) {
    long long nx = x + dx[i];
    long long ny = y + dy[i];
    if (nx < 0) nx += n;
    if (ny < 0) ny += m;
    nx = nx % n;
    ny = ny % m;
    res += (v[nx][ny] == h);
  }
  return res;
}
vector<long long> srtl(vector<long long> v, long long mx) {
  vector<long long> pockets(mx + 1);
  for (long long i = 0; i < (long long)v.size(); i++) {
    pockets[v[i]]++;
  }
  long long k = 0;
  for (long long i = 0; i < (long long)pockets.size(); i++) {
    while (pockets[i] > 0) {
      v[k] = i;
      pockets[i]--;
      k++;
    }
  }
  return v;
}
vector<long long> maxr(vector<long long> v, long long n) {
  long long mx = -1e18;
  vector<long long> maxr(n, -1e18);
  for (long long i = n - 1; i >= 0; i--) {
    mx = max(mx, v[i]);
    maxr[i] = mx;
  }
  return maxr;
}
vector<long long> maxl(vector<long long> v, long long n) {
  long long mx = -1e18;
  vector<long long> maxl(n, -1e18);
  for (long long i = 0; i < n; i++) {
    mx = max(mx, v[i]);
    maxl[i] = mx;
  }
  return maxl;
}
string in_chr(long long n) {
  string s = "";
  while (n > 0) {
    s += (char)(n % 10) + 48;
    n /= 10;
  }
  return s;
}
void solve() {
  long long a, b;
  cin >> a >> b;
  if (a < b) {
    z = a;
    a = b;
    b = z;
  }
  if ((a - b) % 2 == 1) {
    cout << -1 << endl;
    return;
  }
  if (a == b) {
    if (a == 0) {
      cout << 0 << endl;
    } else {
      cout << 1 << endl;
    }
  } else {
    cout << 2 << endl;
  }
}
signed main() {
  long long u;
  cin >> u;
  while (u--) {
    solve();
  }
}

```