You are given two arrays of positive integers $$$a$$$ and $$$b$$$, both of length $$$n$$$. You will perform the following operation exactly $$$n - 1$$$ times:

let $$$m$$$ be the current length of $$$a$$$ and $$$b$$$, note that the lengths will always be equal.
select an integer $$$i$$$ ($$$1 \le i \lt m$$$):
- let $$$S$$$ be the multiset $$$\{a_i, a_{i + 1}, b_i, b_{i + 1}\}$$$
- sort the elements of $$$S$$$ such that $$$s_1 \le s_2 \le s_3 \le s_4$$$.
- now replace $$$a_i, a_{i + 1}$$$ with $$$s_2$$$ and $$$b_i, b_{i + 1}$$$ with $$$s_3$$$. More formally, replace $$$a$$$ with $$$[a_1,a_2,\ldots,a_{i - 1},s_2,a_{i + 2},\ldots,a_m]$$$, and replace $$$b$$$ with $$$[b_1,b_2,\ldots,b_{i - 1},s_3,b_{i + 2},\ldots,b_m]$$$.

After performing all operations, there will be exactly $$$1$$$ element remaining in both $$$a$$$ and $$$b$$$. Determine the maximum value of $$$\min(a_1, b_1)$$$ attainable if you perform operations optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each testcase contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_{n}$$$ ($$$1 \le a_i \le 2 \cdot n$$$).

The third line of each testcase contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_{n}$$$ ($$$1 \le b_i \le 2 \cdot n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each testcase, output the maximum value of $$$\min(a_1,b_1)$$$ attainable.

Note

In the first example, we do not need to perform any operations, so the answer is just $$$\min(1, 2)$$$ which is $$$1$$$.

For the second example, we can do the following sequence of moves:

select $$$i = 1$$$ and then:
- $$$S = \{2, 4, 1, 3\}$$$, $$$s_1 = 1$$$, $$$s_2 = 2$$$, $$$s_3 = 3$$$, $$$s_4 = 4$$$
- $$$a = [\color{red}{2, 4}, 5] \rightarrow [\color{red}{2}, 5]$$$
- $$$b = [\color{red}{1, 3}, 6] \rightarrow [\color{red}{3}, 6]$$$
select $$$i = 1$$$ and then
- $$$S = \{2, 5, 3, 6\}$$$, $$$s_1 = 2$$$, $$$s_2 = 3$$$, $$$s_3 = 5$$$, $$$s_4 = 6$$$
- $$$a = [\color{red}{2, 5}] \rightarrow [\color{red}{3}]$$$
- $$$b = [\color{red}{3, 6}] \rightarrow [\color{red}{5}]$$$

The answer is then $$$\min(3, 5)$$$ which is $$$3$$$, it can be proven that this is optimal.

Me When Median Problem

Examples