题目内容

监测系统记录了一串长度为 $m$ 的读数 $v_1,v_2,\dots,v_m$，并给定正整数门槛 $w$。

从中挑出若干读数（保持相对先后次序）组成一条监测列。称这条监测列分差达标，当且仅当：在其中任意取出三个互不相同下标上的读数 $x,y,z$，都有

$|x-y|+|x-z|+|y-z| \ge w$。

若挑出的读数不足三个，则直接判定为分差达标。

请求出：原读数序列里，分差达标的监测列最长能有多长。

【说明】这里的监测列对应从原序列删去若干项（也可一个都不删）后剩下的序列。

输入描述

第一行一个整数 $g$（$1\le g\le 10^5$），表示询问组数。

接下来共有 $g$ 组数据，每一组格式如下：

第一行一个整数 $m$（$1\le m\le 2\times 10^5$），表示读数个数。

第二行一个整数 $w$（$1\le w\le 10^9$），表示分差门槛。

第三行 $m$ 个整数 $v_1,v_2,\dots,v_m$（$1\le v_i\le 10^9$），表示各次读数。

保证同一文件内所有 $m$ 之和不超过 $5\times 10^5$。

输出描述

输出一行，包含 $g$ 个整数，相邻整数之间用单个空格隔开。

第 $t$ 个数表示第 $t$ 组询问中，分差达标监测列的最大长度。

样例1

输入

3
6
8
3 7 1 12 4 9
3
100
1 2 3
5
6
10 10 10 10 10

输出

5 2 2

说明

第一组：门槛 $w=8$。取读数 $3,7,1,12,9$（对应原序列去掉 $4$）长度为 $5$，任意三个读数的两两绝对差之和都不小于 $8$；若六个全取，则 $1,3,4$ 不满足条件。

第二组：只有三个读数且两两绝对差之和为 $4$，小于 $100$，故最长只能取 $2$。

第三组：全部读数相同，任意三个都不达标，故最长为 $2$。