There are ~n~ people in the queue. The people are numbered ~1,\ldots,n~: each person holds a number ~a_i~. Starting from the second person served, if the person served immediately before him/her holds number ~x~, and the person holds ~y~, it will generate a cost of ~\texttt{xor}(x,y)~ where ~\texttt{xor}~ denotes the bitwise exclusive OR of ~x~ and ~y~. The total cost will be the sum of the costs resulting from serving all ~n~ people in the queue. Formally, assume in the actual order of people served, the numbers they have are ~b_1,\ldots,b_n~, the resulting cost will be

$$\displaystyle \sum_{i=2}^n \texttt{xor}(b_{i-1},b_i).$$

Now you want to reorder the queue so that the total cost is minimized. In other words, you don't have to serve people in exact order of the queue. The caveat is for each person ~i~, it has a tolerance level ~t_i~: if a person has position ~j~ in the original queue, and ~j > i + t_i~, then person ~i~ will become angry if ~j~ is served before ~i~. You cannot let this happen. Under this constraint, what the minimum cost will be?

To compute ~\texttt{xor}(x, y)~, write ~x~ and ~y~ in binary, and for each bit, we compute the corresponding bit in ~\texttt{xor}(x,y)~ using the rule that ~\texttt{xor}(0,0) = \texttt{xor}(1,1) = 0~ and ~\texttt{xor}(0,1) = \texttt{xor}(1,0) = 1~. In other words, the ~i~-th bit of ~\texttt{xor}(x,y)~ in binary is 1 if and only if the ~i~-th bit of ~x~ and ~y~ are different. In C/C++, this is represented by operator ^. For example, to compute ~\texttt{xor}(7,5)~, you can do the following:

• Write ~7~ and ~5~ in binary: ~7 = (111)_2, 5 = (101)_2~.
• For each bit, check if they differ: starting from the least significant (rightmost) bit, we see ~1~ and ~1~ are the same, ~1~ and ~0~ are different, while ~1~ and ~1~ are same again.
• As a result, ~\texttt{xor}(7,5) = (010)_2 = 2~.

Input Specification

The first line consists of an integer ~T~ ~(1 \leq T \leq 5)~ denoting the number of test cases.

For each test case, the first line consists of a positive integer ~n~ ~(1 \leq n \leq 1000)~ denoting the number of students in the queue.

Next, there are ~n~ lines, each line has two non-negative integers ~a_i, t_i~ ~(0 \leq a_i \leq 1000, 0 \leq t_i \leq 7)~ separated by a single space denoting the number person ~i~ holds and the tolerance level of person ~i~.

Output Specification

For each test case, output a line with an integer denoting the minimum cost.

Sample Input

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

Sample Output

16
2

Explanation

In the first case, the optimal ordering is ~3 \to 2 \to 1 \to 4 \to 5~. The total cost is thus

$$\displaystyle \texttt{xor}(12,4) + \texttt{xor}(4,5) + \texttt{xor}(5, 3) + \texttt{xor}(3,2) = 8 + 1 + 6 + 1 = 16.$$

In the second case, the only possible order is ~1 \to 2~, which generates a cost of ~\texttt{xor}(7,5) = 2~.

Constraints

For all test cases, ~1 \leq n \leq 1000~, ~0 \leq a_i \leq 1000~, ~0 \leq t_i \leq 7~, and ~T \leq 5~.

Scoring

There are 25 test cases for this problem.

This table summarizes the bounds of the test cases:

Test case	~n \leq~	~t_i \leq~	~a_i \leq~
1	6	2	1000
2	8	3	16
3	10	1	32
4	12	4	128
5	16	7	1000
6	18	1
7	20	1	128
8		5	32
9	400	1	128
10	500	6	1000
11		7
12	600	2	16
13		3	200
14	700	1	64
15		4	512
16		7	1000
17	800	1	128
18		2	32
19	900	1	200
20		6	512
21	1000	1	1000
22		5	32
23		6	600
24		7	128
25		7	1000