E. 不减的数组
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

DingDing 给了你一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个大于 $$$1$$$ 的正整数 $$$k$$$，你可以对数组 $$$a$$$ 中任何一个元素进行任意次如下操作:

$$$$$$ a_i:=\lfloor \frac{a_i}{k}\rfloor $$$$$$

其中 $$$\lfloor b\rfloor$$$ 的意思是对于 $$$b$$$ 向 $$$0$$$ 取整，例如 $$$\lfloor \frac{7}{3}\rfloor=2$$$，$$$\lfloor -\frac{4}{3}\rfloor=-1$$$。

他想问你，要使得数组单调不减，你最少需要使用多少次操作。

Input

第一行，一个整数 $$$t(1\le t \le 10^4)$$$ ，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,k(1\le n \le 2·10^5;2\le k \le 10^9)$$$，代表数组 $$$a$$$ 的长度。

第二行，一个长度为 $$$n$$$ 的数组 $$$a$$$，数组中每个数字 $$$a_i$$$ 满足 $$$-10^9\le a_i\le 10^9$$$。

保证在同一测试点内的 $$$\sum n\le 2·10^5$$$。

Output

对于每组数据，输出一行整数代表你使得数组单调不减的最少操作次数。

事实上，可以证明，在有限的操作次数内，一定存在一种方式，使得数组最后单调不减。

Example
Input
4
5 2
-7 0 1 3 4
4 3
1 7 3 2
5 100
99 -98 101 0 -100
6 6
1 1 -4 -5 1 4
Output
0
4
6
4