题目描述

在选举问题中，总共有n个小团体，每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半，则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是：在其所在的获胜联盟中，如果缺少了这个小团体的加入，则此联盟不能成为获胜联盟。一个小团体的权利指数是指：一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。

输入格式

输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为一个正整数n（0<n<=20）。第二行有n个正整数，分别表示1到n号小团体的票数。

输出格式

对每组测试数据，在同一个行按顺序输出1到n号小团体的权利指数。

样例

样例输入

2
1
10
7
5 7 4 8 6 7 5

样例输出

1
16 22 16 24 20 22 16

数据范围与提示

1≤每个团体的票数≤100

1≤T≤20