The final exam is here, and it's now or never for Ethan. His current grade is
abysmal so he needs a strong showing on this exam to have any chance of
passing his introductory computer science class.

The exam has only one question: devise an algorithm to compute the compactness
of a grid tree.

Ethan recalls that a "grid tree" is simply an unweighted tree with 2**N**
nodes that you can imagine being embedded within a 2x**N** grid. The top row
of the grid contains the nodes 1 ... **N** from left to right, and the bottom
row of the grid contains the nodes (**N** \+ 1) ... 2**N** from left to right.
Every edge in a grid tree connects a pair of nodes which are adjacent in the
2x**N** grid. Two nodes are considered adjacent if either they're in the same
column, or they're directly side-by-side in the same row. There must be
exactly 2**N**-1 edges that connect the 2**N** nodes to form a single tree.
Additionally, the _i_th node in the grid tree is labelled with an integer
**Ai**.

What was "compactness" again? After some intense thought, Ethan comes up with
the following pseudocode to compute the compactness, **c**, of a grid tree:

* 1\. Set **c** to be equal to 0.
* 2\. Iterate _i_ upwards from 1 to 2**N** \- 1:
* 2a. Iterate _j_ upwards from _i_+1 to 2**N**:
* 2b. Increase **c** by **Ai** * **Aj** * `ShortestDistance(i, j)`
* 3\. Output **c**.

`ShortestDistance(i, j)` is a function which returns the number of edges on
the shortest path from node _i_ to node _j_ in the tree, which Ethan has
implemented correctly. In fact, his whole algorithm is quite correct for once.
This is exactly how you compute compactness!

There's just one issue — in his code, Ethan has chosen to store **c** using a
rather small integer type, which is at risk of overflowing if **c** becomes
too large!

Ethan is so close! Feeling sorry for him, you'd like to make some last-minute
changes to the tree in order to minimize the final value of **c**, and thus
minimize the probability that it will overflow in Ethan's program and cost him
much-needed marks. You can't change any of the node labels **A1..2N**, but you
may choose your own set of 2**N** \- 1 edges to connect them into a grid tree.

For example, if **A** = [1, 3, 2, 2, 4, 5], then the grid of nodes looks like
this:

You'd like to determine the minimum possible compactness which Ethan's program
can produce given a valid tree of your choice. For example, one optimal tree
for the above grid of nodes (which results in the minimum possible compactness
of 198) is as follows:

### Input

Input begins with an integer **T**, the number of trees. For each tree, there
are three lines. The first line contains the single integer **N**. The second
line contains the **N** space-separated integers **A1..N**. The third line
contains the **N** space-separated integers **AN+1..2N**.

### Output

For the _i_th tree, output a line containing "Case #_i_: " followed by the
minimum possible output of Ethan's program.

### Constraints

1 ≤ **T** ≤ 80
1 ≤ **N** ≤ 50
1 ≤ **Ai** ≤ 1,000,000

### Explanation of Sample

One optimal tree for the first case is given above. For that tree, Ethan's
program would compute **c** as the sum of the following values (with some
values omitted):

* **A1** * **A2** * `ShortestDistance(1, 2)` = 1 * 3 * 1 = 3
* **A1** * **A3** * `ShortestDistance(1, 3)` = 1 * 2 * 4 = 8
* ...
* **A1** * **A6** * `ShortestDistance(1, 6)` = 1 * 5 * 3 = 15
* **A2** * **A3** * `ShortestDistance(2, 3)` = 3 * 2 * 3 = 18
* ...
* **A4** * **A6** * `ShortestDistance(4, 6)` = 2 * 5 * 2 = 20
* **A5** * **A6** * `ShortestDistance(5, 6)` = 4 * 5 * 1 = 20

In the second case, there's only one possible tree, for which **c** = 2 * 3 *
1 = 6.

In the third case, two of the four possible trees are optimal (the ones
omitting either the topmost or leftmost potential edge).