DreamGrid 刚刚在他的右口袋里发现了一个斐波那契数列 $f_1, f_2, \dots$ 以及两个整数 $a$ 和 $b$，其中 $f_k$ 表示斐波那契数列的第 $k$ 项。

请告诉 DreamGrid $\sum_{i=a}^{b} f_i$ 是偶数还是奇数。

回想一下，斐波那契数列是一个满足 $f_1 = 1, f_2 = 1$ 且对于所有 $i \ge 3$ 满足 $f_i = f_{i-1} + f_{i-2}$ 的无限数列。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约 100），表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $a$ 和 $b$ ($1 \le a \le b < 10^{10000}$)，其含义如上所述。

输出格式

对于每组测试数据，输出一行。如果 $\sum_{i=a}^{b} f_i$ 是偶数，输出 “0”（不含引号）；如果 $\sum_{i=a}^{b} f_i$ 是奇数，输出 “1”（不含引号）。

样例

输入格式 1

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

输出格式 1

0
0
1
0
0
1

说明

斐波那契数列的前几项为：$f_1 = 1, f_2 = 1, f_3 = 2, f_4 = 3, f_5 = 5, f_6 = 8 \dots$