Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4135
Coolbits

Time Limit: 1 Second      Memory Limit: 65536 KB

Given $n$ intervals $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$, one must select an integer from each of the intervals and calculate their bitwise and value $b$. What's the maximum possible $b$ one can get?

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of intervals.

For the following $n$ lines, the $i$-th line contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^9$), indicating the $i$-th interval.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

Output

For each test case output one line containing one integer, indicating the maximum possible $b$ one can get.

Sample Input

2
3
0 8
2 6
3 9
1
1 100

Sample Output

6
100

Hint

For the first sample test case, one can select 7, 6 and 7 from the three intervals and get their bitwise and value 6.


Author: WENG, Caizhi
Source: The 2019 ICPC China Shaanxi Provincial Programming Contest
Submit    Status