{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid 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.\u003c/p\u003e\n\n\u003cp\u003ePlease tell DreamGrid if $\\displaystyle\\sum_{i\u003da}^b f_i$ is even or is odd.\u003c/p\u003e\n\n\u003cp\u003eRecall that a Fibonacci sequence is an infinite sequence which satisfies $f_1 \u003d 1$, $f_2 \u003d 1$ and $f_i \u003d f_{i-1} + f_{i-2}$ for all $i \\ge 3$.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere 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:\u003c/p\u003e\n\n\u003cp\u003eThe first and only line contains two integers $a$ and $b$ ($1 \\le a \\le b \u0026lt; 10^{10000}$). Their meanings are described above.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line. If $\\displaystyle\\sum_{i\u003da}^b f_i$ is even output \"0\" (without quotes); If $\\displaystyle\\sum_{i\u003da}^b f_i$ is odd output \"1\" (without quotes).\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\n1 2\n1 3\n1 4\n1 5\n123456 12345678987654321\n123 20190427201904272019042720190427\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n0\n1\n0\n0\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eThe first few elements of the Fibonacci sequence are: $f_1 \u003d 1$, $f_2 \u003d 1$, $f_3 \u003d 2$, $f_4 \u003d 3$, $f_5 \u003d 5$, $f_6 \u003d 8$...\u003c/p\u003e\n"}}]}