定义 $f(a_1, a_2, \dots, a_n)$ 如下：

1. 考虑序列 $\{a_1, a_2, \dots, a_n\}$ 的所有 $2^n$ 个子序列；
2. 对于每个子序列，计算其中所有元素的按位异或和；
3. 定义 $f$ 为上述阶段得到的 $2^n$ 个按位异或和之和。

例如，$f(1, 2, 3) = 0 + 1 + 2 + 3 + (1 \oplus 2) + (1 \oplus 3) + (2 \oplus 3) + (1 \oplus 2 \oplus 3) = 12$。其中 $a \oplus b$ 表示整数 $a$ 和 $b$ 的按位异或。

考虑所有满足 $l \le a_i \le r$ 的参数组合，计算 $f(a_1, \dots, a_n)$ 的值。在这些值中，共有多少个不同的数字？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含整数 $n, l$ 和 $r$ ($1 \le n \le 100, 0 \le l \le r \le 10^{18}$)。

输出格式

对于每个测试用例，输出一行，包含一个整数：问题的答案。

样例

输入格式 1

3
2 10 11
3 1 3
3 3 4

输出格式 1

2
3
3