#216751. [GKS 2020 #A] Workout

Tambourine has prepared a fitness program so that she can become more fit! The program is made of sessions. During the -th session, Tambourine will exercise for minutes. The number of minutes she exercises in each session are strictly increasing.

The difficulty of her fitness program is equal to the maximum difference in the number of minutes between any two consecutive training sessions.

To make her program less difficult, Tambourine has decided to add up to additional training sessions to her fitness program. She can add these sessions anywhere in her fitness program, and exercise any positive integer number of minutes in each of them. After the additional training session are added, the number of minutes she exercises in each session must still be strictly increasing. What is the minimum difficulty possible?

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing the two integers and . The second line contains integers, the -th of these is , the number of minutes she will exercise in the -th session.

For each test case, output one line containing Case #x: y, where is the test case number (starting from 1) and is the minimum difficulty possible after up to additional training sessions are added.

样例输入 1

1
3 1
100 200 230

样例输出 1

Case #1: 50

样例输入 2

3
5 2
10 13 15 16 17
5 6
9 10 20 26 30
8 3
1 2 3 4 5 6 7 10

样例输出 2

Case #1: 2
Case #2: 3
Case #3: 1

In Sample Case #1: Tambourine can add up to one session. The added sessions are marked in bold: 100 150 200 230. The difficulty is now 50.

Limits

.

For at most test cases, .

For all other test cases, .

.

for all .

Test Set 1

.

Test Set 2

.