Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4108
Fibonacci in the Pocket

Time Limit: 1 Second      Memory Limit: 65536 KB

DreamGrid has just found a Fibonacci sequence $f_1, f_2, \dots$ and two integers $a$ and $b$ in his right pocket, where $f_k$ indicates the $k$-th element in the Fibonacci sequence.

Please tell DreamGrid if $\displaystyle\sum_{i=a}^b f_i$ is even or is odd.

Recall that a Fibonacci sequence is an infinite sequence which satisfies $f_1 = 1$, $f_2 = 1$ and $f_i = f_{i-1} + f_{i-2}$ for all $i \ge 3$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ (about 100), indicating the number of test cases. For each test case:

The first and only line contains two integers $a$ and $b$ ($1 \le a \le b < 10^{10000}$). Their meanings are described above.

Output

For each test case output one line. If $\displaystyle\sum_{i=a}^b f_i$ is even output "0" (without quotes); If $\displaystyle\sum_{i=a}^b f_i$ is odd output "1" (without quotes).

Sample Input

6
1 2
1 3
1 4
1 5
123456 12345678987654321
123 20190427201904272019042720190427

Sample Output

0
0
1
0
0
1

Hint

The first few elements of the Fibonacci sequence are: $f_1 = 1$, $f_2 = 1$, $f_3 = 2$, $f_4 = 3$, $f_5 = 5$, $f_6 = 8$...


Author: WENG, Caizhi
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status