소수와 XOR? 말도 안 돼

$\mathbb{P}_{LR} = \mathbb{P} \cap [L;R]$라고 정의한다. 여기서 $\mathbb{P}$는 소수의 집합이다. 즉, $\mathbb{P}_{LR}$은 $L$ 이상 $R$ 이하인 모든 소수의 집합이다.

$L$과 $R$이 주어졌을 때, $\mathbb{P}_{LR}$의 부분집합(공집합 포함) 중 하나의 XOR로 나타낼 수 있는 정수의 개수를 구하라.

첫째 줄에 정수 $T$ ($1 \le T \le 100$)가 주어진다. 이는 처리할 테스트 케이스의 개수이다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 정수 $L$과 $R$ ($2 \le L \le R \le 10^{12}$)로 이루어진다.

각 테스트 케이스에 대해 답을 한 줄에 하나씩 출력한다.

첫 번째 예제에서 $\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$

두 번째 예제에서는 $\mathbb{P}_{LR} = \varnothing$이므로 0만 XOR로 나타낼 수 있다.