問題文

$x > y$ を満たす正整数 $x, y$ に対し，中心が等しい半径 $x$ の円 A と半径 $y$ の円 B の $2$ つの円からなる平面図形を，「$(x, y)$-ドーナツ」と呼びます．

例として，$(3, 2)$-ドーナツを図示すると，以下のようになります．

Bob は，誕生日のプレゼントとして，$L \leq i \leq R$ かつ $1 \leq j < i$ を満たす整数組 $(i, j)$ のそれぞれについて，$(i, j)$-ドーナツを $1$ 個ずつ貰いました．

正の倍率の拡大・縮小によって互いに一致させられるドーナツを同一の種類のドーナツとみなし，互いに一致させられないドーナツを別の種類のドーナツとみなすとき，Bob が貰ったドーナツの種類数を求めてください．

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

なお，各テストケースにおいて，$L, R$ は暗号化された状態でそれぞれ整数 $\alpha, \beta$ として与えられます．各テストケースでは，以下のようにして $L, R$ を復号してから解答してください．

• $\mathrm{ans}_0 = 0, \mathrm{ans}_i=$（$i$ 番目のテストケースの答え）とする．このとき，$i$ 番目のテストケースに対して，$L = \alpha \oplus \mathrm{ans}_{i - 1}, R = \beta \oplus \mathrm{ans}_{i - 1}$ のように復号できる．

ただし，$x \oplus y$ で $x$ と $y$ のビット単位 XOR を表します．

制約

• 入力はすべて整数である．
• $1 \leq T \leq 10^5$
• $0 \leq \alpha, \beta \leq 10^{18}$
• $2 \leq L \leq R \leq 2 \times 10^5$

入力

入力は以下の形式で標準入力から与えられる．ここで，$\mathrm{case}_i$ は $i$ 番目のテストケースを表す．

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられる．

$\alpha$ $\beta$

出力

$T$ 行出力せよ．$i$ 行目には，$i$ 番目のテストケースについての答えを出力せよ．

サンプル

5
2 3
1 7
15 15
11 200009
12158598942 12158743847

3
5
9
12158598917
10159235125