409962: GYM103870 G XOR Fun

Peach and Goma have taken up a new hobby recently. Sometimes they decide to get together to look at a number $$$x$$$ and compute $$$x \oplus (x + 1)$$$, where $$$\oplus$$$ is the bitwise XOR operator. Today they computed this value for all integers from $$$A$$$ to $$$B$$$ inclusive, and Peach and Goma are curious about their results. For a given number $$$M$$$ they would like you to find the number of integers $$$x$$$ ($$$A \leq x \leq B$$$) such that $$$x \oplus (x + 1) \geq M$$$.

The first line contains one integer, $$$T$$$ $$$(1 \leq T \leq 10^3)$$$, the number of test cases. Then $$$T$$$ test cases follow.

Each test case has a single line with the integers $$$A$$$, $$$B$$$, $$$M$$$ respectively, where ($$$1 \leq A \leq B \leq 10^9$$$, $$$1 \leq M \leq 10^9$$$).

$$$T$$$ lines with one integer each denoting the number of integers $$$x$$$ ($$$A \leq x \leq B$$$) such that $$$x \oplus (x + 1) \geq M$$$ for each test case.

2
3 5 2
15 20 10

2
1

Note that $$$3 \oplus 4 = 7$$$, $$$4 \oplus 5 = 1$$$, and $$$5 \oplus 6 = 3$$$, therefore there are two integers where the computed value is greater than $$$2$$$.

$$$-------------------------------------------------$$$

Idea: Bossologist

Preparation: Bossologist

Occurences: Novice 7, Intermediate 4, Advanced 2