Algorithm

A. A Variety of Operations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 (1t1041≤�≤104). Description of the test cases follows.

The only line of each test case contains two integers c and d (0c,d109)(0≤�,�≤109), 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−1 if it is impossible to achieve this using the described operations.

Example
input
Copy
6
1 2
3 5
5 3
6 6
8 0
0 0

output
Copy
-1
2
2
1
2
0

Note

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

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

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<iostream>
using namespace std;

int main(){
int n, p, q, count;
cin>>n;
for(int i = 0; i < n; i++){
cin>>p;
cin>>q;
if((p+q)%2 != 0){
cout<<-1<<endl;
}
else if(p == 0 && q == 0){
cout<<0<<endl;
}
else if(p == q){
cout<<1<<endl;
}
else{
cout<<2<<endl;

}

}
return 0;
}
Copy The Code &

Input

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

Output

cmd
-1
2
2
1
2
0