定义 $P_{L,R} = \mathbb{P} \cap [L; R]$，其中 $\mathbb{P}$ 是素数集合。换句话说，$P_{L,R}$ 是区间 $[L, R]$ 内所有素数的集合。

给定 $L$ 和 $R$，求有多少个整数可以表示为 $P_{L,R}$ 的某个（可能为空的）子集的异或和（XOR）。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$) — 表示需要处理的独立测试用例的数量。接下来是 $T$ 个测试用例的描述。

每个测试用例的描述包含两个整数 $L$ 和 $R$ ($2 \le L \le R \le 10^{12}$)。

输出格式

对于每个测试用例，在单独的一行中输出答案。

样例

输入样例 1

3
2 10
999999940 1000000000
2 1000000000000

输出样例 1

8
1
1099511627776

说明

在第一个样例中，$P_{L,R} = \{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$

在第二个样例中，$P_{L,R} = \emptyset$，因此只有 $0$ 可以被表示为某个子集的异或和。