J. Synchronized Archives
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Edward and Sawaha are two brilliant scientists working at a secret data research facility.

Recently, they uncovered two ancient digital archives containing encrypted energy frequencies.

For security reasons, both archives contain an identical number of data elements. Edward manages the first archive, which can be represented as an array $$$A$$$, while Sawaha is in charge of the second archive, represented as an array $$$B$$$.

To unlock the core secret of these frequencies, Edward and Sawaha need to synchronize the data by forming pairs.

A pair is created by matching exactly one element from Edward's archive with exactly one element from Sawaha's archive. Each element from either archive can be used at most once, meaning that no element can belong to more than one pair.

The power value of a synchronized pair containing the elements $$$a$$$ and $$$b$$$ is calculated as their product ($$$a \times b$$$). The entire system will stabilize only if they can select a certain number of pairs such that every single selected pair has a power value greater than or equal to the total number of selected pairs.Edward and Sawaha want to achieve the maximum possible level of system stability.

Your task is to help them determine the maximum integer $$$x$$$ such that it is possible to choose at least $$$x$$$ completely disjoint pairs, where the product of the elements in each chosen pair is at least $$$x$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — 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 elements in each of the two archives.

The second line of each test case contains space-separated integers $$$A_1, A_2, \dots$$$ — representing the values in Edward's archive.The third line of each test case contains space-separated integers $$$B_1, B_2, \dots$$$ — representing the values in Sawaha's archive.

It is guaranteed that the total number of elements across all test cases does not exceed $$$2 \times 10^5$$$, and each individual element in both archives has a value between $$$1$$$ and $$$10^9$$$ inclusive.

Output

For each test case, output a single integer — the maximum possible value of $$$x$$$ that Edward and Sawaha can achieve.

Example
Input
2
4
2 5 1 4
3 1 3 2
3
1 2 1
1 1 2
Output
3
2
Note

In the first test case:Edward's archive contains the elements: $$$A = [2, 5, 1, 4]$$$.

Sawaha's archive contains the elements: $$$B = [3, 1, 3, 2]$$$.We want to find the maximum integer $$$x$$$ such that we can form at least $$$x$$$ disjoint pairs, and the product of each pair is $$$\ge x$$$.

Let us test if it is possible to achieve $$$x = 3$$$:To achieve $$$x = 3$$$, we need to form at least $$$3$$$ pairs, and the product of each pair must be greater than or equal to $$$3$$$. We can strategically pair the elements as follows:First Pair: Match element $$$5$$$ from Edward's archive with element $$$3$$$ from Sawaha's archive.$$$$$$\text{Product} = 5 \times 3 = 15 \quad (\text{Since } 15 \ge 3, \text{ this pair is valid})$$$$$$Second Pair: Match element $$$4$$$ from Edward's archive with element $$$2$$$ from Sawaha's archive.$$$$$$\text{Product} = 4 \times 2 = 8 \quad (\text{Since } 8 \ge 3, \text{ this pair is valid})$$$$$$Third Pair: Match element $$$2$$$ from Edward's archive with element $$$3$$$ from Sawaha's archive.$$$$$$\text{Product} = 2 \times 3 = 6 \quad (\text{Since } 6 \ge 3, \text{ this pair is valid})$$$$$$We successfully formed $$$3$$$ valid disjoint pairs where every pair's product is $$$\ge 3$$$.It is impossible to choose $$$4$$$ disjoint pairs that all satisfy a product $$$\ge 4$$$ because the remaining unused elements are $$$1$$$ (from Edward) and $$$1$$$ (from Sawaha), which would result in a product of $$$1 \times 1 = 1 \lt 4$$$.Therefore, the maximum possible value of $$$x$$$ for the first case is $$$3$$$.