In 2017, Google learned about a serious Android bug: in the burger emoji, the cheese was directly on top of the lower bun, rather than on the patty itself. Really, who makes a burger that way? Sundar, our CEO, vowed to drop everything and address this issue immediately.

To prevent this sort of situation in the future, the Code Jam team has
constructed a mathematical model for understanding burgers. A burger consists
of a stack of **K** ingredients between two buns, with each ingredient
appearing exactly once. We are interested in the *distance-to-bun* value
of each ingredient. The distance-to-bun value of an ingredient is the minimum
number of other ingredients between the that ingredient and a bun:

- If
**K**is even, then the distance-to-bun values for the ingredients (starting with the ingredient at the top of the stack) are: 0, 1, ...,**K**/2 - 1,**K**/2 - 1, ..., 1, 0. - If
**K**is odd, then they are: 0, 1, ..., ((**K**- 1) / 2) - 1, (**K**- 1) / 2, ((**K**- 1) / 2) - 1, ..., 1, 0.

After carrying out a lot of focus group testing (and eating a lot of
burgers), we have determined that the i-th of each of our **K**
ingredients has an optimal distance-to-bun value of **D _{i}**. We
think our burger emoji users will be happiest if we choose an ordering for
our ingredients that minimizes the

For example, if we have five ingredients A, B, C, D, and E with
optimal distance-to-bun values of 0, 2, 1, 1, and 2, and we place them
between the buns in that order, then the error is (0-0)^{2} +
(2-1)^{2} + (1-2)^{2} + (1-1)^{2} + (2-0)^{2}
= 6. If we instead place them in the order C, E, B, D, A, then the error is
(1-0)^{2} + (2-1)^{2} + (2-2)^{2} + (1-1)^{2}
+ (0-0)^{2} = 2, which turns out to be the minimum possible error
for these ingredients.

Given the list of optimal distance-to-bun values for our ingredients, can you help us determine the smallest possible error?

The first line of the input gives the number of test cases, **T**;
**T** test cases follow. Each begins with one line containing an integer
**K**: the number of ingredients in our burger. Then, there is one more
line containing **K** integers **D _{i}**, the optimal
distance-to-bun values of our ingredients.

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is the smallest possible error, as described above.

1 ≤ **T** ≤ 100.

0 ≤ **D _{i}** ≤ floor((

1 ≤ **K** ≤ 8.

1 ≤ **K** ≤ 100.

3 5 0 2 1 1 2 1 0 6 2 2 2 2 2 2

Case #1: 2 Case #2: 0 Case #3: 10

Sample Case #1 is the one illustrated in the problem statement.

In Sample Case #2, there is only one ingredient in the burger; that is not much of a burger, but our model has to be able to handle this base case! There is no confusion over how to place the one ingredient, and the error is 0.

In Sample Case #3, there are six ingredients, but all of them have an
optimal distance-to-bun of 2. Any way of placing them is equivalent, and the
error is 2^{2} + 1^{2} + 0^{2} + 0^{2} +
1^{2} + 2^{2} = 10.

Subtask | Score |
---|---|

1 | 35 |

2 | 65 |

3 | 0 |