Little F's school is located in a remote corner of the city, and all students have to eat at the school cafeteria. Although the cafeteria is simple, the chef can always prepare dishes that satisfy the students. Of course, different people have different tastes, but everyone's taste can be represented by a non-negative integer.

Due to limited staff, the cafeteria can only prepare a dish for one person at a time. The time required to prepare each dish depends on the previous dish. If the taste of the previous dish was $a$ and the current one is $b$, the time required to prepare the current dish is $(a \text{ or } b) - (a \text{ and } b)$. The first dish prepared does not require any time to calculate. Here, "or" and "and" represent the bitwise OR and bitwise AND operations, respectively.

Since there are many students in the school, preparing meals often takes a significant amount of time. Therefore, the cafeteria occasionally does not prepare meals in the order of the queue to reduce the total time.

Although the students understand this practice, each student has a certain tolerance level. Specifically, the $i$-th student in the queue allows at most $B_i$ students immediately behind them to receive their meals first. If any student after that receives their meal before the current student, the current student will become very angry. Therefore, the cafeteria must also consider the students' emotions when preparing meals.

Now, Little F wants to know the minimum time required for the school cafeteria to finish preparing all the dishes while satisfying everyone's tolerance.

Input

The first line contains a positive integer $C$, representing the number of test cases.

For each test case, the first line contains a positive integer $N$, representing the number of students.

Starting from the second line of each test case, there are $N$ lines, each containing two space-separated non-negative integers $T_i$ and $B_i$, representing the taste of the dish required by the $i$-th student in the queue and their tolerance, respectively.

There are no extra blank lines between test cases.

Output

The output contains $C$ lines, each containing an integer representing the minimum time required for the cafeteria to complete all dishes for the corresponding test case.

Examples

Input 1

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

Output 1

16
1

Note

For the first test case: Student 1 allows student 2 or student 3 to receive their meal before them; student 2 allows student 3 to receive their meal before them; student 3 is quite stingy and must receive their meal before the students behind them... One optimal strategy is to prepare dishes in the order: student 3, student 2, student 1, student 4, student 5. The time required for each dish is 0, 8, 1, 6, and 1, respectively.

Constraints

For 30% of the data, $1 \le N \le 20$. For 100% of the data, $1 \le N \le 1,000$, $0 \le T_i \le 1,000$, $0 \le B_i \le 7$, $1 \le C \le 5$. There exists 30% of the data where $0 \le B_i \le 1$. There exists 65% of the data where $0 \le B_i \le 5$. There exists 45% of the data where $0 \le T_i \le 130$.