You are given two numbers N1 and N2. You need to find out if the product of these numbers generate an even number or an odd number.

Input Format
The first line of the input contains a single integer T, denoting the number of test cases. Then T test cases follow. Each test case contains two lines of input:-
The first line contains N1
The second line contains N2

Output Format
For each test case, Print 1 or 0 according to the result. if even print 1 else print 0.

Constraints
1<=T<=120
1<=N1,N2<=1099

Sample Input
3
5
8
2
98
773
13

Sample Output 1 1 0