辛酸风味 题目描述 Haruna 正在制作黑暗料理，虽然她并没有这个自觉。 她选定了 n 种食材，以及这 n 种食材的使用量，第 i 种食材的使用量记为 ai​。 Ayaka 自然知道 Harun

辛酸风味

题目描述

Haruna 正在制作黑暗料理，虽然她并没有这个自觉。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

她选定了 n 种食材，以及这 n 种食材的使用量，第 i 种食材的使用量记为 ai​。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

Ayaka 自然知道 Haruna 的厨艺如何。趁着 Haruna 暂时离开挑选新食材，她需要调整食材的使用量使菜品的味道变得中和。Ayaka 每次调整可以选择一种食材，将这种食材的使用量增加 11。一道菜品的味道是中和的，当且仅当所有食材使用量的平均数和中位数相同。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

Ayaka 认为食材使用量的中位数是其中第 ⌊2n+1​⌋ 小的数。例如 [2,4,1,3] 的中位数是 22，而 [3,1,5] 的中位数是 3。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

Ayaka 需要尽快让菜品的味道变得中和，所以她希望调整的次数尽量少。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当然 Haruna 不止做了一道菜，所以 Ayaka 需要对每一道菜做出调整。她请你求出对于每道菜，最少需要调整多少次才能变得中和。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式

第一行一个正整数 T，代表菜品数量。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来每道菜品用两行描述。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第一行一个正整数 n，表示菜品使用的食材数量。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第二行 n 个用空格分隔的正整数，第 i 个数表示 ai​。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式

共 T 行，第 i 行表示使第 i 道菜品变得中和的最少操作次数。bX8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

数据范围

• 对于30% 的数据，1≤T≤100，1≤n≤20，1≤ai​≤10^3；
• 对于另外 30% 的数据，保证{ai​} 的中位数大于平均数；
• 对于 100% 的数据，1≤T≤2⋅10^5，1≤n,∑n≤2⋅10^5，1≤ai​≤10^9。

样例数据