AT_pakencamp_2023_day3_j XOR

$ 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 $ となります。）

入力は以下の形式で標準入力から与えられます。 > $ T $ $ \mathrm{test}_1 $ $ \mathrm{test}_2 $ $ \vdots $ $ \mathrm{test}_T $ ここで、 $ \mathrm{test}_i $ は $ i $ 番目のテストケースの情報を表し、次の形式で与えられます。 > $ L $ $ R $

各テストケースに対する答えを改行区切りで順に出力してください。 それぞれのテストケースについて、総 XOR としてありえる整数の数を出力してください。

### Sample Explanation 1 $ 1 $ つめのテストケースについて説明します。総 XOR としてありえる整数は $ 0,1,2,3,8,9,10,11 $ の $ 8 $ つです。例えば、 $ \lbrace 8,9,10\rbrace $ の部分集合として $ \lbrace 8,10\rbrace $ を選べば総 XOR が $ 2 $ になります。 ### Constraints - $ 1\leq T\leq 2\times 10^5 $ - $ 0\leq L\leq R\lt 2^{60} $