시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB222100.000%

문제

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.

예제 입력 1

3
2 10
999999940 1000000000
2 1000000000000

예제 출력 1

8
1
1099511627776

노트

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.