题目描述

传奇魔法师 FF 在研究魔法对植物生长的影响。

FF 大师认为每种魔法都有一个描述其和植物亲和度的参数 $\alpha$，表示植物将在此魔法下每秒钟生长 $\alpha$ 米。

FF 大师在实验室中架设了一台相机，每秒钟会拍摄一张照片。但是植物的生长太缓慢了，相机的分辨率只有 $1$ 微米，经常拍不清楚。即第 $k$ 秒测量的植物生长数据是 $\lfloor k\alpha \rfloor$ 微米。

若两个植物在此前的所有记录有一个不同，就称这两个植物就是可区分的。FF 大师已经测量好所有魔法的植物亲和度 $a_i$，他想要知道什么时候所有植物都可以互相区分，他才可以结束实验。

输入描述

第一行有一个整数 $T$，其中 $1 \leqslant T \leqslant 10^4$，表示测试组数。

对于每一组测试数据，第一行有两个整数 $n, w$，其中 $n$ 表示实验的组数，$w$ 是一个系数。保证 $2 \leqslant n \leqslant 10^4, 1 \leqslant w \leqslant 10^{9}$。

接下来一行有 $n$ 个整数 $A_1, \cdots, A_n$，其中 $1 \leqslant A_i \leqslant 10^9$，表示第 $i$ 组实验的植物亲和度为 $a_i = A_i / w$。保证 $a_i$ 互不相同。

保证 $\sum n \leqslant 2 \times 10^4$。

输出描述

请在每行中输出一个整数，表示结束时间。

样例

3
2 10
3 4
5 10
1 2 3 4 5
2 1000000
1 2

3
5
500000

提示

对于第 $1$ 组数据：亲和度分别为 $0.3$ 和 $0.4$，因此在前 $3$ 秒的情况是

$$\begin{aligned} \lfloor 0.3 \rfloor, \lfloor 0.6 \rfloor, \lfloor 0.9 \rfloor \\ \lfloor 0.4 \rfloor, \lfloor 0.8 \rfloor, \lfloor 1.2 \rfloor \end{aligned} $$

故第 $3$ 秒即可区分所有的魔法。