Migrated from Lutece 576 Journey

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In Tomb-sweeping Festival, Yangsir and her friends planned to have a journey in a park. The park has N attractions which form a circle and only between adjacent attractions there is a road, so there are $N$ roads in total. On the way to the park, Yangsir and her friends lost their way. After several twists and turns, they arrived at the park but they still didn't know which attraction they are on now.

Looking at the park's map, Yangsir wanted to know that: if they set attraction $X$ as starting point, what is the minimum time they needed to pass all N attractions at least once? They don't need to go back to the starting attraction and the time spend on attractions are ignored.

We number the $N$ attractions from $1$ to $N$ clockwise, and the $i_{th}$ road is the road between $i_{th}$ and $i+1_{th}$ attraction, except that the $N_{th}$ road is the road between $N$ and $1$. The $N$ roads are all undirected.

Input

There are multiple test cases. The first line of the input will be an integer $T$ ($T \leq 10$) indicating the number of test cases.

For each test case, the first line is only one integer $N$ ($3 \leq N \leq 1000$), representing the number of attractions in the park. In the second line there are $N$ positive integers separated by one space representing the time needed to pass through the $i_{th}$ road. All the integers above are within $1,000,000$.

Output

For each test case, print Case #t: first, in which $t$ is the number of the test case starting from $1$. Then output $N$ integers separated by one space which are the minimum time needed if they start from $1_{st}$ attraction, $2_{nd}$ attraction,..., $N_{th}$ attraction.

Samples

1
5
4 6 5 3 7

Case #1: 18 19 19 20 18

Resources

10th UESTC Programming Contest Final