J - XOR Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

T 個のテストケースについて、以下の問題を解いてください。

非負整数 L,R\,(L\leq R) が与えられます。\lbrace L,L+1,\ldots,R\rbrace の部分集合を 1 つ選ぶとき、その集合に含まれる数の総 XOR としてありえる整数はいくつありますか？ただし、0 個の数の XOR は 0 とします。

XOR の定義 非負整数 x,y に対し、ビットごとの排他的論理和 x\operatorname{XOR}y は以下のように定義されます。
  • x\operatorname{XOR}y を 2 進法で表現したときの 2^k の位の数は、x と y を2 進法で表現したときの 2^k の位の数が一方のみ 1 である場合 1 で、そうでない場合 0。
例えば、5\operatorname{XOR}6=3 です。（2 進法表記だと 101\operatorname{XOR}110=11 となります。）

制約

  • 1\leq T\leq 2\times 10^5
  • 0\leq L\leq R\lt 2^{60}

入力

入力は以下の形式で標準入力から与えられます。

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

ここで、\mathrm{test}_i は i 番目のテストケースの情報を表し、次の形式で与えられます。

L R

出力

各テストケースに対する答えを改行区切りで順に出力してください。

それぞれのテストケースについて、総 XOR としてありえる整数の数を出力してください。

入力例 1

3
8 10
2 2
123 456

出力例 1

8
2
512

1 つめのテストケースについて説明します。総 XOR としてありえる整数は 0,1,2,3,8,9,10,11 の 8 つです。例えば、\lbrace 8,9,10\rbrace の部分集合として \lbrace 8,10\rbrace を選べば総 XOR が 2 になります。