马斯卡彭小蛋糕太好吃了，所以贪吃的 zyfgg 和 zcygg 在实验室偷吃马斯卡彭蛋糕，但是因为害怕不给 hzcgg 留点儿会让他生气，所以他们决定留下一个蛋糕。
zyfgg 认为留下最大的马斯卡彭蛋糕可以让 hzcgg 更开心，所以他每次会吃掉相邻两个马斯卡彭蛋糕中更小的一个；而 zcygg 认为留一个就算留，所以他每次会吃掉相邻两个马斯卡彭蛋糕中更大的一个。
实验室里有 n 个马斯卡彭蛋糕，a _i 代表第 i 个蛋糕的大小，zyfgg 希望最后最大化留下的蛋糕，而 zcygg 希望最后最小化留下的蛋糕。如果双方都完全按照自己的想法轮流吃蛋糕，zyfgg 先吃，请你求出留给 hzcgg 的蛋糕的大小。
hzcgg正在吃马斯卡彭：
tle="" align="" />

每个测试包含多个测试用例。 第一行包含测试用例数 t（1 ≤ t ≤ 10 ⁵ ）。 测试用例说明如下。
每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 10 ⁵ ）,代表马斯卡彭蛋糕数量。
每个测试用例的第二行包含 n 个整数 a ₁ ,a ₂ ,...,a _n （1 ≤ a _i ≤10 ⁵ ），代表蛋糕大小。
保证所有测试用例中 n 的总和不超过 10 ⁵ 。

对于每个测试用例，输出一个整数，代表剩下的马斯卡彭蛋糕的大小。