该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定 $n$ 个物品，每个物品都有价值 $v_{i}$ ， $v_{i}$ 只有 $0, 1$ 两种取值情况，你需要从里面选择恰好 $k$ 个物品。记所选物品价值的最大值为 $max$，所选物品价值的中位数为 $mid$，请问 $max - mid$ 的最小值是多少？

【中位数】一个长度 n 的序列 $\left\{a_{1},a_{2},\ldots,a_{n}\right\}$ 的中位数为其从小到大排序后的第 $\left\lfloor\frac{n+1}{2}\right\rfloor$ 个元素

输入格式

本题有多组测试数据

第一行输入一个整数 $t(1 \leq t \leq 100)$ ，表示数据组数

对于每组测试数据：

第一行输入两个整数 $n$, $k$ ( $1 \leq n \leq 1000$ , $1 \leq k \leq n$ )

第二行输入 $n$ 个整数 $v_{i}(0 \leq v_{i} \leq 1)$ ，表示物品价值

输出格式

对于每组测试数据，输出 $max - mid$ 的最小值

样例

3
4 1
0 1 0 1
5 4
0 0 0 1 1
4 3
0 1 0 1

0
1
0

样例解释 1

• 对于第一组测试数据，可以选择 $0$；$max - mid = 0 - 0 = 0$

• 对于第二组测试数据，可以选择 $0, 0, 0, 1$；$max - mid = 1 - 0 = 1$

• 对于第三组测试数据，可以选择 $0, 1, 1$；$max - mid = 1 - 1 = 0$