問題文

正整数 $x$ に対して、 関数 $f(x)$ を $f(x) =$（$x$ の正の約数の総和）として定めます。

$2$ つの正整数 $L, \ R$ $(L \leq R)$ が与えられるので、 $\displaystyle \sum_{k = L}^{R}f(k)$ を $2$ で割ったあまりを求めてください。

テストケースが $T$ 個与えられるので、それぞれについて解いてください。

制約

• 入力は全て整数
• $1 \leq T \leq 10^4$
• $1 \leq L \leq R \leq 10^{15}$

入力

入力は標準入力から与えられる。 $1$ 行目は以下の形式で与えられる。

$T$

以下、 $T$ 行にわたって $T$ 個のテストケースがそれぞれ以下の形式で与えられる。

$L$ $R$

出力

$T$ 行にわたって出力せよ。$i$ $(1 \leq i \leq T)$ 行目には、 $i$ 番目のテストケースの答えを出力せよ。

最後に改行すること。

サンプル

6
1 4
2 5
2 2
123456 654321
123456789 987654321
1 1000000000000000

1
0
1
0
1
1