题目描述

Haruna 正在制作黑暗料理，虽然她并没有这个自觉。

她选定了 $n$ 种食材，以及这 $n$ 种食材的使用量，第 $i$ 种食材的使用量记为 $a_i$。

Ayaka 自然知道 Haruna 的厨艺如何。趁着 Haruna 暂时离开挑选新食材，她需要调整食材的使用量使菜品的味道变得中和。Ayaka 每次调整可以选择一种食材，将这种食材的使用量增加 $1$。一道菜品的味道是中和的，当且仅当所有食材使用量的平均数和中位数相同。

Ayaka 认为食材使用量的中位数是其中第 $\left\lfloor \frac{n+1}2 \right\rfloor$ 小的数。例如 $[2,4,1,3]$ 的中位数是 $2$，而 $[3,1,5]$ 的中位数是 $3$。

Ayaka 需要尽快让菜品的味道变得中和，所以她希望调整的次数尽量少。

当然 Haruna 不止做了一道菜，所以 Ayaka 需要对每一道菜做出调整。她请你求出对于每道菜，最少需要调整多少次才能变得中和。

输入格式

第一行一个正整数 $T$，代表菜品数量。

接下来每道菜品用两行描述。

第一行一个正整数 $n$，表示菜品使用的食材数量。

第二行 $n$ 个用空格分隔的正整数，第 $i$ 个数表示 $a_i$。

输出格式

共 $T$ 行，第 $i$ 行表示使第 $i$ 道菜品变得中和的最少操作次数。

3
4
1 1 3 3
3
1 2 3
4
1 9 1 9

4
0
8

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 100$，$1 \le n \le 20$，$1 \le a_i \le 10^3$；
• 对于另外 $30\%$ 的数据，保证 $\{a_i\}$ 的中位数大于平均数；
• 对于 $100\%$ 的数据，$1 \le T \le 2 \cdot 10^5$，$1 \le n, \sum n \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$。