新年已经来到硕士协助中心，这意味着是时候推出一个新功能了！

现在，学生们可以参加远程学习课程，总共有 $n$ 门课程可供选择。对于第 $i$ 门远程学习课程，学生可以获得的成绩范围是从 $x_i$ 到 $y_i$。

然而，并非所有课程都对每个学生开放。具体来说，第 $j$ 个学生只能访问编号从 $l_j$ 到 $r_j$ 的课程，也就是说，课程编号为 $l_j, l_j+1, \dots, r_j$ 的远程学习课程。

远程学习课程的创建者决定用一种特殊的方式来确定最终成绩。假设第 $j$ 个学生在他们的远程学习课程中获得的成绩为 $c_{l_j}, c_{l_j+1}, \dots, c_{r_j}$。那么他们的最终成绩将等于：

其中 $|$ 表示按位或运算。

由于用于解决远程学习课程的聊天机器人坏了，学生们向您寻求帮助。对于 $q$ 个学生中的每一个，请告诉他们能够获得的最大最终成绩。

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$）—— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 远程学习课程的数量。

接下来的 $n$ 行中，每行包含两个整数 $x_i$ 和 $y_i$（$0 \le x_i \le y_i < 2^{30}$）—— 第 $i$ 门课程可以获得的最低和最高成绩。

下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）—— 学生的数量。

接下来的 $q$ 行中，每行包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）—— 第 $j$ 个学生可以访问的最小和最大课程编号。

保证所有测试用例的 $n$ 之和以及所有测试用例的 $q$ 之和都不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出 $q$ 个整数，其中第 $j$ 个整数是第 $j$ 个学生可以获得的最大最终成绩。

示例

输入

3
2
0 1
3 4
3
1 1
1 2
2 2
4
1 7
1 7
3 10
2 2
5
1 3
3 4
2 3
1 4
1 2
6
1 2
2 2
0 1
1 1
3 3
0 0
4
3 4
5 5
2 5
1 2

输出

1 5 4 
15 11 15 15 7 
1 3 3 3 

注意

在第一个测试用例中：

• 第一个学生能获得的最大成绩是 $1$：
  在第一门远程学习课程中，他将获得成绩 $1$。
  因此，最终成绩是 $1$。

• 第二个学生能获得的最大成绩是 $5$：
  在第一门远程学习课程中，他将获得成绩 $1$。
  在第二门远程学习课程中，他将获得成绩 $4$。
  因此，最终成绩是 $1 \;|\; 4 = 5$。

• 第三个学生能获得的最大成绩是 $4$：
  在第二门远程学习课程中，他将获得成绩 $4$。
  因此，最终成绩是 $4$。

在第二个测试用例中：

• 第一个学生能获得的最大成绩是 $15$：
  在第一门远程学习课程中，他将获得成绩 $7$。
  在第二门远程学习课程中，他将获得成绩 $4$。
  在第三门远程学习课程中，他将获得成绩 $8$。
  因此，最终成绩是 $7 \;|\; 4 \;|\; 8 = 15$。

• 第二个学生能获得的最大成绩是 $11$：
  在第三门远程学习课程中，他将获得成绩 $9$。
  在第四门远程学习课程中，他将获得成绩 $2$。
  因此，最终成绩是 $9 \;|\; 2 = 11$。