The New Year has arrived in the Master's Assistance Center, which means it's time to introduce a new feature!

Now students are given distance learning courses, with a total of $$$n$$$ courses available. For the $$$i$$$-th distance learning course, a student can receive a grade ranging from $$$x_i$$$ to $$$y_i$$$.

However, not all courses may be available to each student. Specifically, the $$$j$$$-th student is only given courses with numbers from $$$l_j$$$ to $$$r_j$$$, meaning the distance learning courses with numbers $$$l_j, l_j + 1, \ldots, r_j$$$.

The creators of the distance learning courses have decided to determine the final grade in a special way. Let the $$$j$$$-th student receive grades $$$c_{l_j}, c_{l_j + 1}, \ldots, c_{r_j}$$$ for their distance learning courses. Then their final grade will be equal to $$$c_{l_j}$$$ $$$|$$$ $$$c_{l_j + 1}$$$ $$$|$$$ $$$\ldots$$$ $$$|$$$ $$$c_{r_j}$$$, where $$$|$$$ denotes the bitwise OR operation.

Since the chatbot for solving distance learning courses is broken, the students have asked for your help. For each of the $$$q$$$ students, tell them the maximum final grade they can achieve.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of distance learning courses.

Each of the following $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i \le y_i \lt 2^{30}$$$) — the minimum and maximum grade that can be received for the $$$i$$$-th course.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$) — the number of students.

Each of the following $$$q$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the minimum and maximum course numbers accessible to the $$$j$$$-th student.

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$q$$$ over all test cases do not exceed $$$2\cdot10^5$$$.

Output

For each test case, output $$$q$$$ integers, where the $$$j$$$-th integer is the maximum final grade that the $$$j$$$-th student can achieve.

Note

In the first test case:

The maximum grade for the first student is $$$1$$$:
- On the first distance learning course, he will receive a grade of $$$1$$$.
Therefore, the final grade is $$$1$$$.
The maximum grade for the second student is $$$5$$$:
- On the first distance learning course, he will receive a grade of $$$1$$$.
- On the second distance learning course, he will receive a grade of $$$4$$$.
Therefore, the final grade is $$$1$$$ $$$|$$$ $$$4$$$ $$$=$$$ $$$5$$$.
The maximum grade for the third student is $$$4$$$:
- On the second distance learning course, he will receive a grade of $$$4$$$.
Therefore, the final grade is $$$4$$$.

In the second test case:

The maximum grade for the first student is $$$15$$$:
- On the first distance learning course, he will receive a grade of $$$7$$$.
- On the second distance learning course, he will receive a grade of $$$4$$$.
- On the third distance learning course, he will receive a grade of $$$8$$$.
Therefore, the final grade is $$$7$$$ $$$|$$$ $$$4$$$ $$$|$$$ $$$8$$$ $$$=$$$ $$$15$$$.
The maximum grade for the second student is $$$11$$$:
- On the third distance learning course, he will receive a grade of $$$9$$$.
- On the fourth distance learning course, he will receive a grade of $$$2$$$.
Therefore, the final grade is $$$9$$$ $$$|$$$ $$$2$$$ $$$=$$$ $$$11$$$.

Idx	Name	Rating
A	Entertainment in MAC	800
B	Informatics in MAC	1200
C	Messenger in MAC	1800
D	Exam in MAC	1800
E	Distance Learning Courses in MAC	2400
F	Andrey's Tree	2800

Codeforces Round 932 (Div. 2)