山中的伊娜

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

山路上依次站着 $n$ 只章鱼，编号为 $1,2,\ldots,n$。第 $i$ 只章鱼的初始生命值为 $a_i$，且 $1\le a_i\le 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

样例解释

第一个测试用例可以依次操作区间 $[1,3]$ 和 $[2,2]$。

第二个测试用例可以依次操作区间 $[1,7]$、$[2,6]$、$[3,5]$ 和 $[4,4]$。

数据范围

$1\le t\le10^5$，$1\le n\le2\times10^5$，$1\le k\le10^9$，$1\le a_i\le k$；所有测试用例的 $n$ 之和不超过 $2\times10^5$。

令 $b_i=a_i\bmod k$。