题目描述

在选举问题中，总共有 $n$ 个小团体，每个小团体拥有一定数量的选票数。如果其中 $m$ 个小团体的票数和超过总票数的一半，则此组合为“获胜联盟”。$n$ 个团体可形成若干个获胜联盟。

一个小团体要成为一个“关键加入者”的条件是：在其所在的获胜联盟中，如果缺少了这个小团体的加入，则此联盟不能成为获胜联盟。一个小团体的权利指数是指：一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。

输入格式

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个正整数 $n$，表示小团体的数量。
• 第二行输入 $n$ 个正整数，分别表示 $1$ 到 $n$ 号小团体的票数。

输出格式

对于每组测试数据，输出一行 $n$ 个整数，依次表示 $1$ 到 $n$ 号小团体的权利指数。

样例 #1

2
1
10
3
5 7 5

1
2 2 2

样例解释

对于第二组数据： 3 个小团体的票数分别为 $5, 7, 5$。总票数为 $17$，半数为 $8.5$，获胜联盟的票数和需 $\ge 9$。 可能的联盟组合及关键加入者如下：

• $\{1, 2\}$（票数 $12$）：缺少 $1$（剩 $7<9$），缺少 $2$（剩 $5<9$）。关键加入者：$1, 2$。
• $\{2, 3\}$（票数 $12$）：缺少 $2$（剩 $5<9$），缺少 $3$（剩 $7<9$）。关键加入者：$2, 3$。
• $\{1, 3\}$（票数 $10$）：缺少 $1$（剩 $5<9$），缺少 $3$（剩 $5<9$）。关键加入者：$1, 3$。
• $\{1, 2, 3\}$（票数 $17$）：缺少任意一个，剩余票数仍 $\ge 9$，无关键加入者。

统计关键加入者次数：

• 1 号：在 $\{1, 2\}, \{1, 3\}$ 中成为关键加入者，权利指数为 $2$。
• 2 号：在 $\{1, 2\}, \{2, 3\}$ 中成为关键加入者，权利指数为 $2$。
• 3 号：在 $\{2, 3\}, \{1, 3\}$ 中成为关键加入者，权利指数为 $2$。

数据范围

• $1 \le T \le 100$
• $1 \le n \le 20$
• $1 \le \text{票数} \le 1000$