给定一个包含 $n$ 个元素的序列 $A$，其中第 $i$ 个元素记为 $A[i]$。此外，还有一个整数 $K$ 作为系数。现在考虑若干次查询。

在每次查询中，给定两个整数 $L$ 和 $R$，表示序列 $A$ 中从第 $L$ 个元素到第 $R$ 个元素的子序列。你可以从该子序列中选择若干个元素，记为 $A[i_1], A[i_2], \dots, A[i_t]$。根据你的选择，可以得到值 $Z$： $$Z = K \oplus (A[i_1] \oplus A[i_2] \oplus \dots \oplus A[i_t])$$ 你需要做出最优选择，使得 $Z$ 的值最大。

输入格式

输入包含多组测试数据，第一行是一个整数 $T$ ($1 \le T \le 10$)，表示测试数据的组数。

对于每组测试数据，第一行包含三个整数 $N, Q$ 和 $K$ ($1 \le N \le 10000, 1 \le Q \le 100000, 0 \le K \le 100000$)。第二行包含 $N$ 个整数，表示 $A[1]$ 到 $A[N]$，其中每个元素满足 $0 \le A[i] \le 10^8$。接下来 $Q$ 行，每行包含两个整数 $L$ 和 $R$ ($1 \le L \le R \le N$)，描述一次查询。

所有测试数据中 $N$ 的总和不超过 $20000$，所有测试数据中 $Q$ 的总和不超过 $200000$。

输出格式

对于每次查询，输出一行，包含 $Z$ 的最大值。

样例

输入样例 1

1
5 3 0
1 2 3 4 5
1 3
2 4
3 5

输出样例 1

3
7
7