31157번 - Primes and XOR? Nonsense 다국어

문제

Define $\mathbb{P}_{LR} = \mathbb{P} \cap [L;R],ドル where $\mathbb{P}$ is the set of prime numbers. In other words, $\mathbb{P}_{LR}$ is the set of all primes between $L$ and $R$ inclusive.

Given $L$ and $R,ドル find the number of integers that can be represented as XOR of some (possibly empty) subset of $\mathbb{P}_{LR}$.

입력

The first line of input contains one integer $T$ (1ドル \le T \le 100$) --- the number of independent test cases you need to process. Descriptions of $T$ test cases follow.

The description of one test case consists of two integers $L$ and $R$ (2ドル \le L \le R \le 10^{12}$).

출력

For each test case print the answer on a separate line.

제한

노트

In the first example, $\mathbb{P}_{LR} = \{ 2, 3, 5, 7 \}$.

• 0ドル = 2 \oplus 5 \oplus 7$
• 1ドル = 2 \oplus 3$
• 2ドル = 2$
• 3ドル = 3$
• 4ドル = 3 \oplus 7$
• 5ドル = 2 \oplus 7$
• 6ドル = 3 \oplus 5$
• 7ドル = 7$

In the second example, $\mathbb{P}_{LR} = \varnothing,ドル so only 0ドル$ can be represented as XOR of some subset.