L. Primes and XOR? Nonsense
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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}$$$.

Input

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}$$$).

Output

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

Example
Input
3
2 10
999999940 1000000000
2 1000000000000
Output
8
1
1099511627776
Note

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.