Minimum Scalar Product (Small)

You are given two vectors $v_1 = (x_1, x_2, \dots, x_n)$ and $v_2 = (y_1, y_2, \dots, y_n)$. The scalar product of the two vectors is a single number, computed as $x_1 y_1 + x_2 y_2 + \dots + x_n y_n$.

You may permute the coordinates of each vector however you like. Choose two permutations that make the scalar product of the resulting vectors as small as possible, then print that minimum scalar product.

The first line contains the number of test cases $T$. For each test case, the first line contains an integer $n$, and the next two lines contain $n$ integers each, giving the coordinates of $v_1$ and $v_2$ in order.

Limits

• $1 \le T \le 1000$
• $1 \le n \le 8$
• $-1000 \le x_i, y_i \le 1000$

For each test case, print one line

Case #X: Y

where $X$ is the test case number starting from 1, and $Y$ is the minimum scalar product over all permutations of the two given vectors.