对于某些正整数 $$$m$$$,YunQian 认为 $$$2m$$$(可能是负)整数的数组 $$$q$$$ 是好的,当且仅当对于 $$$q$$$ 的每个可能的长度为 $$$m$$$ 的子序列,子序列中 $$$m$$$ 元素的乘积等于$$$m$$$ 不在子序列中的元素。形式上,令 $$$U=\{1,2,\ldots,2m\}$$$。对于所有集合$$$S \subseteq U$$$,使得$$$|S|=m$$$,$$$\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$$$。
将长度为 $$$k$$$ 的两个数组 $$$a$$$ 和 $$$b$$$ 之间的距离定义为 $$$\sum\limits_{i=1}^k|a_i-b_i|$$$。
给定一个正整数 $$$n$$$ 和一个由 $$$2n$$$ 整数组成的数组 $$$p$$$。
在所有长度为 $$$2n$$$ 的好数组 $$$q$$$ 上查找 $$$p$$$ 和 $$$q$$$ 之间的最小距离。对于所有正整数 $$$n$$$ 都可以显示,至少存在一个好的数组。请注意,您不需要构造达到此最小距离的数组 $$$q$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot10^5$$$)。
每个测试用例的第二行包含 $$$2n$$$ 整数 $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$|p_i| \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$p$$$ 和好的 $$$q$$$ 之间的最小距离。
示例
输入 #1
4 1 6 9 2 1 2 2 1 2 -2 -2 2 2 4 -3 -2 -1 0 1 2 3 4
输出 #1
3 2 5 13
注意
在第一个测试用例中,最好让 $$$q=[6,6]$$$。
在第二个测试用例中,最好让 $$$q=[2,2,2,2]$$$。