Migrated from Lutece 1496 C

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

Ruins is driving a car to participating in a programming contest. As on a very tight schedule, he will drive the car without any slow down, so the speed of the car is non-decrease real number.

Of course, his speeding caught the attention of the traffic police. Police record $N$ positions of Ruins without time mark, the only thing they know is every position is recorded at an integer time point and Ruins started at $0$.

Now they want to know the minimum time that Ruins used to pass the last position.

Input

First line contains an integer $T$ ($1\le T\le 100$), which indicates the number of test cases.

Every test case begins with an integers $N$ ($1\le N\le 10^5$), which is the number of the recorded positions.

The second line contains $N$ numbers $a_1, a2, \ldots , a_N$ ($0<a_i\le 10^9,a_i<a_{i+1}$), indicating the recorded positions.

Output

For every test case, you should output Case #x: y, where x indicates the case number and counts from $1$ and y is the minimum time.

Samples

1
3
6 11 21

Case #1: 4

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）