公园里有 $$$n$$$ 棵树,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 树的初始高度为 $$$h_i$$$。
你想给这些树浇水,让它们都长到同样的高度。
浇水过程如下。您从 $$$1$$$ 天开始浇树。在第 $$$j$$$ 天,您可以:
- 选择一棵树并给它浇水。如果日期是奇数(例如 $$$1, 3, 5, 7, \dots$$$),则树的高度增加 $$$1$$$。如果日期是偶数(例如 $$$2, 4, 6, 8, \dots$$$),那么树的高度会增加 $$$2$$$。
- 或者跳过一天而不给任何树浇水。
请注意,一天不能浇水超过一棵树。
你的任务是确定给树木浇水以使它们长到相同高度所需的最少天数。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 树的数量。
测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$),其中 $$$h_i$$$ 是第 $$$i$$$ 树的高度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$ ($$$\sum n \le 3 \cdot 10^5$$$)。
输出
对于每个测试用例,打印一个整数 - 给树木浇水以使它们长到相同高度所需的最少天数。
示例
输入 #1
3 3 1 2 4 5 4 4 3 5 5 7 2 5 4 8 3 7 4
输出 #1
4 3 16
注意
考虑示例的第一个测试用例。树的初始状态是$$$[1, 2, 4]$$$。
1. 第一天,给第一棵树浇水,所以高度的顺序变成$$$[2, 2, 4]$$$;
2. 第二天,给第二棵树浇水,这样高度的顺序就变成$$$[2, 4, 4]$$$;
3.我们跳过第三天;
4. 第四天,我们给第一棵树浇水,这样高度的顺序就变成了$$$[4, 4, 4]$$$。
因此,答案是$$$4$$$。