1225: 小狗
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：88
解决：8
题目描述
如果你认为你的作法正确，却获得了 TLE 40rps,请使用更快的读入方式。
这只小狗很奇怪，它吃饭时是要将食物排成一排从左到右吃的。
如果除第一份外每一份食物都比它左边的食物更美味，则这些食物是修勾满意的。
现在有 $n$ 份食物从左到右排成了一排，编号分别为 $1,2,...,n$，且第 $i$ 份的美味度为 $u_i$。老古会一种魔法，可以将一份食物的美味度变成原来美味度的 $k$ 倍加一。
老古希望你编写一个程序，帮他算算在不改变食物排列的顺序下，他至少要施展几次魔法，才能使小狗满意这些食物。
输入
第一行一个整数 $T$。
本题共有 $T$ 组数据，对于每组数据：
第一行两个整数 $n,k$。
第二行 $n$ 个整数，第 $i$ 个整数表示 $u_i$。
输出
对于每组数据，一行一个整数表示答案。
样例输入 复制
2
6 2
1 1 4 5 1 4
8 3
1 2 3 4 5 6 7 8样例输出 复制
4
0提示
对于 $30\%$ 的数据，满足 $1 \le T \le 10$，且 $k=1$。
对于 $100\%$ 的数据，满足 $1 \le n \le 15$，
$0\leq u_i\le10$,
$1\le k \leq 10$，$1\le T \leq 2\times10^5$。