A. Min Max Swap

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two arrays aa and bb of nn positive integers each. You can apply the following operation to them any number of times:

• Select an index ii (1≤i≤n1≤i≤n) and swap aiai with bibi (i. e. aiai becomes bibi and vice versa).

Find the minimum possible value of max(a1,a2,…,an)⋅max(b1,b2,…,bn)max(a1,a2,…,an)⋅max(b1,b2,…,bn) you can get after applying such operation any number of times (possibly zero).

Input

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤1001≤n≤100) — the length of the arrays.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤100001≤ai≤10000) where aiai is the ii-th element of the array aa.

The third line of each test case contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤100001≤bi≤10000) where bibi is the ii-th element of the array bb.

Output

For each test case, print a single integer, the minimum possible value of max(a1,a2,…,an)⋅max(b1,b2,…,bn)max(a1,a2,…,an)⋅max(b1,b2,…,bn) you can get after applying such operation any number of times.

Example

input

Copy

3
6
1 2 6 5 1 2
3 4 3 2 2 5
3
3 3 3
3 3 3
2
1 2
2 1

output

Copy

18
9
2

Note

In the first test, you can apply the operations at indices 22 and 66, then a=[1,4,6,5,1,5]a=[1,4,6,5,1,5] and b=[3,2,3,2,2,2]b=[3,2,3,2,2,2], max(1,4,6,5,1,5)⋅max(3,2,3,2,2,2)=6⋅3=18max(1,4,6,5,1,5)⋅max(3,2,3,2,2,2)=6⋅3=18.

In the second test, no matter how you apply the operations, a=[3,3,3]a=[3,3,3] and b=[3,3,3]b=[3,3,3] will always hold, so the answer is max(3,3,3)⋅max(3,3,3)=3⋅3=9max(3,3,3)⋅max(3,3,3)=3⋅3=9.

In the third test, you can apply the operation at index 11, then a=[2,2]a=[2,2], b=[1,1]b=[1,1], so the answer is max(2,2)⋅max(1,1)=2⋅1=2max(2,2)⋅max(1,1)=2⋅1=2.

Problem solving instructions ： Water problem , Put a group of small values , Put the big value in another group , The product is the smallest . Traverse the judgment Exchange .

#include<stdio.h>

int main() 
{
	int t;
	int a[101], b[101];
	scanf("%d", &t);
	while (t--) 
	{
		int n, max1 = 0, max2 = 0, temp;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &b[i]);
		}
		for (int i = 0; i<n; i++) 
		{
			if (a[i]<b[i]) 
			{
				temp = a[i];
				a[i] = b[i];
				b[i] = temp;
			}
			if (max1 < a[i])
			{
				max1 = a[i];
			}
			if (max2 < b[i])
			{
				max2 = b[i];
			}
		}

		printf("%d\n", max1*max2);
	}
	return 0;
}