
ZOJ Problem Set  4108
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_{i1} + f_{i2}$ for all $i \ge 3$. InputThere 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. OutputFor 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 Input6 1 2 1 3 1 4 1 5 123456 12345678987654321 123 20190427201904272019042720190427 Sample Output0 0 1 0 0 1 HintThe 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 