#216860. [GKS 2022 #B] Unlock the Padlock

Imagine you have a padlock, which is a combination lock consisting of dials, set initially to a random combination. The dials of the padlock are of size , which means that they can have values between and , inclusive, and can be rotated upwards or downwards. They are also ordered from left to right, with the leftmost and rightmost dials at positions and , respectively. The padlock can be unlocked by setting the values of all its dials to .

You can perform or more operations of this kind:

• Pick any range such that and rotate all the dials in together, upwards or downwards. Rotating up increases the value of each dial in the range by , and rotating down decreases its value by . Note that a dial with value becomes when increased (rotated up) and a dial with value becomes when decreased (rotated down).

The series of operations must satisfy the following condition:

• The range chosen in the -th operation needs to be completely contained within the range chosen in the -th operation; that is, . The initial range can be chosen arbitrarily.

Example of a valid sequence of operations to unlock a padlock with initial combination :

1. Rotate range downwards.
2. Rotate range downwards.
3. Rotate range downwards.

The following are some operations that cannot be performed:

1. Rotating range after , because is not completely contained in (does not satisfy where and ).
2. Rotating range after .

The goal for you is to output the minimum number of valid operations needed to make all dials in the padlock set to .

The first line of the input contains the number of test cases, . test cases follow.

Each test case consists of lines.

The first line of each test case contains integers and , representing the number of dials in the padlock and the size of the dials, respectively.

The second line of each test case contains integers , where the -th integer represents the value of the -th dial in the initial combination of the padlock.

For each test case, output one line containing Case #: , where is the test case number (starting from ) and is the minimum number of operations needed to unlock the padlock as described in the statement.

样例输入 1

2
6 2
1 1 0 1 0 1
6 2
0 1 0 0 1 1

样例输出 1

Case #1: 3
Case #2: 2

样例输入 2

2
6 10
1 1 2 2 3 3
6 10
1 1 9 9 1 1

样例输出 2

Case #1: 3
Case #2: 3

In Sample Case #, the minimum number of operations needed to unlock the padlock is . We can unlock it using the following operations:

1. Rotate range downwards.
2. Rotate range downwards.
3. Rotate range downwards.

In Sample Case #, the minimum number of operations needed to unlock the padlock is . We can unlock it using the following operations:

1. Rotate range upwards.
2. Rotate range downwards.

Limits

.

, for all .

Test Set

.

.

Test Set

.

.

Test Set

.

.