Mushroom Monster (Small)

Kaylin loves mushrooms. Put them on her plate and she eats every one. In this problem she is working through a plate of mushrooms while Bartholomew keeps adding more pieces to it.

We look at the number of mushroom pieces on the plate at 10-second intervals. Bartholomew can put any non-negative integer number of pieces down at any moment, and the only way a piece leaves the plate is by being eaten.

Find the minimum number of pieces Kaylin could have eaten under each of two different methods of computation.

1. Assume Kaylin can eat any number of pieces at any time.
2. Assume that, starting with the first time we look at the plate, Kaylin eats at a constant rate whenever there are mushrooms on her plate.

Consider the observations 10, 5, 15, 5.

Under the first method Kaylin ate at least 15 pieces: she eats 5, then 10 more are put on her plate, then she eats another 10. There is no way she ate fewer.

Under the second method Kaylin ate at least 25 pieces. Her rate has to be at least 1 piece per second. She starts with 10 pieces on the plate. In the first 10 seconds she eats 10 pieces and 5 more are put down. Over the next 5 seconds she eats those 5, the plate stays empty for 5 seconds, and then Bartholomew puts 15 more pieces down. She eats 10 pieces in the last 10 seconds.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case takes two lines. The first line contains a single integer $N$, and the second line contains $N$ space-separated integers $m_i$, the number of mushroom pieces on Kaylin's plate at the start and at each following 10-second interval.

Limits

• $1 \le T \le 100$
• $2 \le N \le 10$
• $0 \le m_i \le 100$

For each test case, output one line in the format Case #x: y z, where $x$ is the test case number starting from 1, $y$ is the minimum under the first method of computation, and $z$ is the minimum under the second method of computation.