给树浇水

题目描述

Y 同学得到了一个长度为 $N$ 的正整数序列 $H = (H_1, H_2, \dots, H_N)$。

Y 同学可以对该序列进行若干次操作，操作按照先后顺序从 $1$ 开始编号。在每一次操作中，Y 同学可以选择执行以下两种动作中的一种：

1. 选择序列中的某一个元素 $H_i$（$1 \le i \le N$）。如果当前是第奇数次操作，则令 $H_i$ 的值增加 $1$；如果当前是第偶数次操作，则令 $H_i$ 的值增加 $2$。
2. 什么也不做（跳过本次操作，但依然会占用一次操作次数）。

Y 同学希望经过若干次操作后，序列中的所有元素都能变得完全相等。请你编写程序帮助 Y 同学计算出，至少需要进行多少次操作才能达成此目标。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个正整数 $N$，表示序列的长度。 第二行包含 $N$ 个正整数 $H_1, H_2, \dots, H_N$，相邻两个整数之间由一个空格隔开，表示给定的整数序列。

输出格式

输出共 $T$ 行。 对于每组测试数据，输出一行一个整数，表示使序列中所有元素变得相等所需要的最少操作次数。

样例

样例输入 #1

3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4

样例输出 #1

4
3
16

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 2 \times 10^4$，$1 \le N \le 3 \times 10^5$，$1 \le H_i \le 10^9$，且所有测试数据中 $N$ 的总和不超过 $3 \times 10^5$。