给定 个物品，每个物品都有价值 ， 只有 两种取值情况，你需要从里面选择恰好 个物品。 记所选物品价值的最大值为 ，所选物品价值的中位数为 ，请问 的最小值是多少？ 【中位数】一个长度 的序列 的中位数为其从小到大排序后的第 个元素。

输入描述:

本题有多组测试数据第一行输入一个整数 ，表示数据组数。对于每组测试数据：第一行输入两个整数 。第二行输入 个整数 ，表示物品价值。

输出描述:

对于每组测试数据，输出 的最小值。