AT_tupc2024_f Another Long Sequence Inversion

非負整数 $ L,R,X $ が二進法で与えられます。長さ $ R-L+1 $ の整数列 $ (L \oplus X,(L+1)\oplus X, \dots, R\oplus X) $ の転倒数を二進法で求めてください。 ただし、 $ \oplus $ はビットごとの排他的論理和を表します。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 転倒数とは 数列 $ B=(B_1,B_2,\dots, B_M) $ の転倒数とは、整数の組 $ 1 \leq i \lt j \leq M $ であって $ B_i \gt B_j $ を満たすものの個数です。 ビットごとの排他的論理和とは 非負整数 $ A,B $ のビットごとの排他的論理和 (XOR) $ A \oplus B $ は、以下のように定義されます。 - $ A \oplus B $ を二進表記した際の $ 2^k \, (k \geq 0) $ の位の数は、 $ A,B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101=110 $ )。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ L $ $ R $ $ X $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 個目のテストケースに対する答えを出力せよ。

### 部分点 追加の制約 $ T \leq 3000, R \lt 2^{30}, X \lt 2^{30} $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 $ L,R,X $ をそれぞれ十進法で表記すると $ L=5,R=8,X=2 $ です。 $ (5\oplus 2, 6\oplus 2, 7\oplus 2, 8\oplus 2)=(7,4,5,10) $ なので求めるべき転倒数は $ 2 $ です。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 0 \leq L \leq R \lt 2^{2 \times 10^5} $ - $ 0 \leq X \lt 2^{2 \times 10^5} $ - 入力は全て整数 - $ T $ は 十進法で与えられる - $ L,R,X $ は二進法で与えられ、先頭に余分な `0` を含まない（ただし $ 0 $ は $ 1 $ 桁の整数とみなす） - $ 1 $ つの入力ファイルに含まれる $ R $ の二進法での桁数の総和は $ 2 \times 10^5 $ 以下 - $ 1 $ つの入力ファイルに含まれる $ X $ の二進法での桁数の総和は $ 2 \times 10^5 $ 以下