For a sequence of N integers, A₁, A₂ ... A_N

We can calculate the stability factor P, as

P = sum of all (abs(A_i - A_i-1) × C[i]) where 2 ≤ i ≤ N

C[i] is the cost of putting a number at position i

Your task is find the minimum P for the given N numbers considering all the different permutations of them.

Input

First line contains an integer T (1 ≤ T ≤ 10) which denotes the total number of test cases. Each test case consists of three lines.

The first line contains the integer N (1 ≤ N ≤ 15). The second line contains a space separated list of N integers (<150) which denote the given set of numbers.

The third line contains a space separated list of N integers. The ith integer on this line denotes the value for C[i] (1 ≤ C[i] < 150)

Output

For each test case, print the minimum possible value of P considering all permutations of the given numbers.

Example

Input:
1
5
1 8 3 6 5
1 2 3 4 5
Output
24

One of the possible permutation of given numbers which has p = 24 is 1, 3, 5, 6, 8