D1. 无限序列（简单版本）

每个测试的时间限制：$2$ 秒
每个测试的内存限制：$256$ MB

这是该问题的简单版本。与困难版本的区别在于，在此版本中 $l = r$。只有解决了所有版本的题目，你才能进行 Hack。

给定一个正整数 $n$ 以及一个无限二进制序列 $a$ 的前 $n$ 项。该序列定义如下：

对于 $m > n$，

$$a_m = a_1 \oplus a_2 \oplus \dots \oplus a_{\lfloor \frac{m}{2} \rfloor} $$

其中 $\oplus$ 表示按位异或运算。

你的任务是计算给定区间 $[l, r]$ 内元素的和：

$$a_l + a_{l+1} + \dots + a_r$$

---

输入格式

每个测试包含多个测试用例。
第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。

每个测试用例的描述如下：

• 第一行包含三个整数 $n, l, r$（$1 \le n \le 2 \times 10^5$，$1 \le l = r \le 10^{18}$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$a_i \in \{0,1\}$）—— 序列 $a$ 的前 $n$ 项。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

---

输出格式

对于每个测试用例，输出一个整数 —— 给定区间内元素的和。

---

示例

输入

9
1 1 1
1
2 3 3
1 0
3 5 5
1 1 1
1 234 234
0
5 1111 1111
1 0 1 0 1
1 1000000000000000000 1000000000000000000
1
10 87 87
0 1 1 1 1 1 1 1 0 0
12 69 69
1 0 0 0 0 1 0 1 0 1 1 0
13 46 46
0 1 0 1 1 1 1 1 1 0 1 1 1

输出

1
1
0
0
1
0
1
0
0

---

说明

• 在第一个测试用例中，序列 $a$ 为
  $[\underline{1},1,1,0,0,1,1,1,1,1,\dots]$，$l=1$，$r=1$。
  区间 $[1,1]$ 的元素和为 $a_1 = 1$。

• 在第二个测试用例中，序列 $a$ 为
  $[1,0,\underline{1},1,1,0,0,1,1,0,\dots]$，$l=3$，$r=3$。
  区间 $[3,3]$ 的元素和为 $a_3 = 1$。