310564: CF1852C. Ina of the Mountain

C. Ina of the Mountaintime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

To prepare her "Takodachi" dumbo octopuses for world domination, Ninomae Ina'nis, a.k.a. Ina of the Mountain, orders Hoshimachi Suisei to throw boulders at them. Ina asks you, Kiryu Coco, to help choose where the boulders are thrown.

There are $n$ octopuses on a single-file trail on Ina's mountain, numbered $1, 2, \ldots, n$. The $i$-th octopus has a certain initial health value $a_i$, where $1 \leq a_i \leq k$.

Each boulder crushes consecutive octopuses with indexes $l, l+1, \ldots, r$, where $1 \leq l \leq r \leq n$. You can choose the numbers $l$ and $r$ arbitrarily for each boulder.

For each boulder, the health value of each octopus the boulder crushes is reduced by $1$. However, as octopuses are immortal, once they reach a health value of $0$, they will immediately regenerate to a health value of $k$.

Given the octopuses' initial health values, find the minimum number of boulders that need to be thrown to make the health of all octopuses equal to $k$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$) – the number of octopuses, and the upper bound of a octopus's health value.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$) – the initial health values of the octopuses.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output the minimum number of boulders that need to be thrown to make the health values of all octopuses equal to $k$.

ExampleInput

2
4 3
1 2 1 3
7 3
1 2 3 1 3 2 1

Output

2
4

Note

In the first test case, the minimum number of boulders thrown is $2$:

• Throw the first boulder between $[l,r] = [1,3]$. Then, the octopuses' health values become $[3, 1, 3, 3]$.
• Throw the second boulder between $[l,r] = [2,2]$. Then, the octopuses' health values become $[3, 3, 3, 3]$.

In the second test case, the minimum number of boulders thrown is $4$. The $[l,r]$ ranges are $[1,7], [2, 6], [3, 5], [4, 4]$.

**题目大意：**
在山上，有编号为1到n的章鱼，每个章鱼有一个初始健康值$a_i$，范围在1到k之间。每次可以投掷一个巨石，巨石会砸中索引从l到r的连续章鱼，每个被砸中的章鱼的健康值会减少1，当健康值减到0时，章鱼会立即恢复到k的健康值。要求计算最少需要投掷多少次巨石，使得所有章鱼的健康值都达到k。

**输入数据格式：**
第一行包含一个整数t，表示测试用例的数量。每个测试用例包含两行，第一行是两个整数n和k，分别表示章鱼的数量和健康值的上限。第二行包含n个整数$a_1, a_2, \ldots, a_n$，表示每个章鱼的初始健康值。

**输出数据格式：**
对于每个测试用例，输出一行，包含一个整数，表示最少需要投掷的巨石数量。

**示例：**
输入：
```
2
4 3
1 2 1 3
7 3
1 2 3 1 3 2 1
```
输出：
```
2
4
```

**注意：**
在第一个测试用例中，最少需要投掷2次巨石：第一次砸中[1,3]号章鱼，健康值变为[3,1,3,3]；第二次砸中[2,2]号章鱼，健康值变为[3,3,3,3]。在第二个测试用例中，最少需要投掷4次巨石，分别砸中[1,7], [2,6], [3,5], [4,4]号章鱼。**题目大意：** 在山上，有编号为1到n的章鱼，每个章鱼有一个初始健康值$a_i$，范围在1到k之间。每次可以投掷一个巨石，巨石会砸中索引从l到r的连续章鱼，每个被砸中的章鱼的健康值会减少1，当健康值减到0时，章鱼会立即恢复到k的健康值。要求计算最少需要投掷多少次巨石，使得所有章鱼的健康值都达到k。 **输入数据格式：** 第一行包含一个整数t，表示测试用例的数量。每个测试用例包含两行，第一行是两个整数n和k，分别表示章鱼的数量和健康值的上限。第二行包含n个整数$a_1, a_2, \ldots, a_n$，表示每个章鱼的初始健康值。 **输出数据格式：** 对于每个测试用例，输出一行，包含一个整数，表示最少需要投掷的巨石数量。 **示例：** 输入： ``` 2 4 3 1 2 1 3 7 3 1 2 3 1 3 2 1 ``` 输出： ``` 2 4 ``` **注意：** 在第一个测试用例中，最少需要投掷2次巨石：第一次砸中[1,3]号章鱼，健康值变为[3,1,3,3]；第二次砸中[2,2]号章鱼，健康值变为[3,3,3,3]。在第二个测试用例中，最少需要投掷4次巨石，分别砸中[1,7], [2,6], [3,5], [4,4]号章鱼。