Inspectors

Yuri owns factories in many Russian cities, and every factory needs one inspection each month. He wants his children to learn the business by running the inspections, and he sets two conditions.

First, each child is assigned at least two different factories, so a child can compare how the factories are run.

Second, the total travel distance has to be as small as possible. A child inspects each assigned factory once a month and returns to the factory the trip started from, so a child's distance is the length of the shortest closed route that visits every assigned factory exactly once. A child assigned exactly two factories travels between them and back, so that child's distance is twice the distance between the two factories.

Yuri is happy to use a single child if that gives the smallest total. With four factories, one layout is cheapest when one child tours all four, and another layout is cheapest when two children take two factories each.

Given the distances between the factories, write a program that finds the smallest possible total travel distance.

The first line contains the number of test cases $m$.

Each test case begins with a line containing the number of factories $n$ ($2 \le n \le 100$). The next $n-1$ lines give the distances between factories. The first of those lines holds $n-1$ values, the distances between factory 1 and factories $2, 3, 4, \dots, n$. The second line holds $n-2$ values, the distances between factory 2 and factories $3, 4, \dots, n$. The remaining lines follow the same pattern.

Every distance is a positive integer, and the distance between any two factories is at most 1000. The distances among any three factories satisfy the triangle inequality.

For each test case print one line in the form Case x: y, where $x$ is the test case number starting at 1 and $y$ is the smallest possible total travel distance.

For a set of $n$ factories, assume that Yuri always has at least $n/2$ children.