有一天,Vlad 开始好奇他可以在地铁的自动扶梯上与谁交谈。总共有 $$$n$$$ 乘客。自动扶梯总共有 $$$m$$$ 梯级,所有梯级索引从 $$$1$$$ 到 $$$m$$$,第 $$$i$$$ 梯级的高度为 $$$i \cdot k$$$。
Vlad 的身高是 $$$H$$$ 厘米。身高为 $$$a$$$ 和 $$$b$$$ 的两个人,如果站在不同的台阶上,并且他们之间的高度差等于台阶之间的高度差,则可以在自动扶梯上进行对话。
例如,如果两个人的身高分别为 $$$170$$$ 和 $$$180$$$ 厘米,并且 $$$m = 10,k = 5$$$,那么他们可以站在编号为 $$$7$$$ 和 $$$5$$$ 的台阶上,其中台阶之间的高度差等于两个人之间的高度差: $$$k \cdot 2 = 5 \cdot 2 = 10 = 180 - 170$$$。还有其他可能的方法。
给定一个大小为 $$$n$$$ 的数组 $$$h$$$,其中 $$$h_i$$$ 表示第 $$$i$$$ 个人的身高。弗拉德感兴趣的是他可以在自动扶梯上单独与多少人交谈。
例如,如果$$$n = 5,m = 3,k = 3,H = 11$$$,并且$$$h = [5, 4, 14, 18, 2]$$$,Vlad可以与身高$$$5$$$的人进行对话(Vlad将站在台阶$$$1$$$上,另一个人将站在台阶上$$$3$$$)和身高为$$$14$$$的人(例如,Vlad可以站在台阶$$$3$$$上,而另一个人将站在台阶$$$2$$$上)。 Vlad 无法与身高 $$$2$$$ 的人进行对话,因为即使他们站在自动扶梯的最极端的台阶上,他们之间的身高差也会是 $$$6$$$,而他们的身高差是 $$$9$$$。 Vlad 无法与自动扶梯上的其他人交谈,因此此示例的答案是 $$$2$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
然后是测试用例的描述。
每个测试用例的第一行包含整数:$$$n, m, k, H$$$ ($$$1 \le n,m \le 50$$$, $$$1 \le k,H \le 10^6$$$)。这里,$$$n$$$是人数,$$$m$$$是步数,$$$k$$$是相邻步之间的高度差,$$$H$$$是Vlad的身高。
第二行包含 $$$n$$$ 整数:$$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^6$$$)。这里,$$$h_i$$$表示第$$$i$$$个人的身高。
输出
对于每个测试用例,输出一个整数 - Vlad 可以在自动扶梯上单独交谈的人数。
示例
输入 #1
7 5 3 3 11 5 4 14 18 2 2 9 5 6 11 9 10 50 3 11 43 44 74 98 62 60 99 4 11 73 4 8 8 49 68 58 82 73 7 1 4 66 18 66 39 83 48 99 79 9 1 1 13 26 23 84 6 60 87 40 41 25 6 13 3 28 30 70 85 13 1 55
输出 #1
2 1 4 1 0 0 3
注意
第一个示例在问题陈述中进行了解释。
在第二个示例中,Vlad 可以与身高 $$$11$$$ 的人进行对话。
在第三个示例中,Vlad 可以与身高为 $$$44, 74, 98, 62$$$ 的人进行对话。因此,答案是$$$4$$$。
在第四个示例中,Vlad 可以与身高 $$$73$$$ 的人进行对话。