You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡想要加训，巡计划了 $n$ 天，第 $i$ 天会做任意一个难度在 $[l_i,r_i]$ 之间的试题。由于巡比较聪明，如果巡做了难度为 $x_1,x_2,\dots,x_m$ 的题，巡的智慧会变为 $x_1\text{ OR }x_2\text{ OR }x_3\text{ OR }\dots\text{ OR }x_m$。其中 $\text{OR}$ 表示二进制下的或运算（即 C++ 中的 | 运算）。

但是巡会偷懒，巡给你 $q$ 个询问，每次给定一个区间 $l,r$ 表示如果只执行 $[l,r]$ 天的计划，那么巡的智慧最高是多少。

输入格式

第一行一个正整数 $T$ 表示测试组数量。

每个测试组一个正整数表示 $n$。

接下来 $n$ 行，每行两个自然数表示 $l_i,r_i$。

接下来一行一个正整数表示 $q$。

接下来 $q$ 行，每行两个正整数表示 $l,r$。

输出格式

对每个测试组，输出一行 $q$ 个正整数表示每个询问的答案。

样例 $1$

【样例输入】

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

样例 $2$

见下发 $\textit{ex\_train2.in/ans}$。

该测试点满足测试点 $2$ 的性质。

数据范围

对所有测试点满足 $T\leq 5$，$0\leq l_i\leq r_i\leq 2^{30}$，$1\leq l\leq r\leq n$。