You are given two arrays A and B both containing N integers. You have to rearrange numbers in A and B such that A[0]*B[0] + A[1]*B[1] + ... + A[n-1]*B[n-1] is minimised. Output that number.

NOTE: that you have do this routine T times.

SCORING: Your score is 100 * correctly solved files / number of files. File is correctly solved if you have solved all T tests correctly.

Constraints

n <= 100000

a[i] <= 10^9

NOTE: result will fit in 64 bit integer. IO is huge, use faster io methods.

Input

First number of input is T number of virtual test cases. Each test starts with number N and 2*N integers donating A and B.

Output

Ouput minimised value

Example

Input:
2
3
1 1 3
1 1 3
2
1 2
1 2

Output:
7
4

Explanation: in first example we can rearrange number (1, 1, 3) and (1, 3, 1) which leads to sum of 7. (1, 2), (2, 1) in the second example