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⁹

NOTE: result will fit in 64 bit integer. I/O is huge, use faster I/O 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

Output 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