Alice 和 Bob 正在玩游戏。黑板上写有$$$n$$$($$$n$$$为偶数)个整数,用$$$x_1、x_2、\ldots、x_n$$$表示。还有一个给定的整数 $$$k$$$ 和一个初始为 $$$0$$$ 的整数分数。游戏持续 $$$\frac{n}{2}$$$ 回合,其中以下事件依次发生:
- Alice 从黑板上选择一个整数并将其擦除。我们将 Alice 选择的整数称为 $$$a$$$。
- Bob 从黑板上选择一个整数并将其擦除。我们将 Bob 选择的整数称为 $$$b$$$。
- 如果 $$$a+b=k$$$,则添加 $$$1$$$ 来得分。
Alice 正在玩游戏以最小化分数,而 Bob 正在玩游戏以最大化分数。假设双方都采用最优策略,游戏结束后得分是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2\cdot 10^5, 1 \leq k \leq 2\cdot n$$$, $$$n$$$ 是偶数)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1,x_2,\ldots,x_n$$$ ($$$1 \leq x_i \leq n$$$) — 黑板上的整数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果两个玩家都发挥最佳,则输出分数。
示例
输入 #1
4 4 4 1 2 3 2 8 15 1 2 3 4 5 6 7 8 6 1 1 1 1 1 1 1 16 9 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
输出 #1
2 1 0 4
注意
在第一个测试用例中,游戏可能进行的一种方式如下:
- Alice 选择 $$$1$$$,Bob 选择 $$$3$$$。分数增加为$$$1+3=4$$$。现在黑板上剩下的两个整数是$$$2$$$ 和$$$2$$$。
- Alice 和 Bob 都选择 $$$2$$$。分数增加为$$$2+2=4$$$。
- 由于黑板上现在没有整数,游戏结束。
在第三个测试用例中,Alice和Bob选择的整数之和不可能为$$$1$$$,所以我们回答$$$0$$$。
请注意,这只是出于演示目的游戏如何进行的示例。这可能不是爱丽丝或鲍勃的最佳策略。