名字的价值

Time Limit: 3000 ms Memory Limit: 200000 KiB

Problem Description

每个人都有名字,名字都是唯一的不存在重复现象。现在假设名字都是由小写字母组成并且长度不超过10,我们赋予每个名字一个初始价值。价值是正整数并且不超过100,如果第j个人的名字是第i个人的前缀并且前缀长度最大,我们就说j是i的父节点,比如:名字A为:a;名字B为ab;名字C为abc; A是C的前缀,B也是C的前缀,但是B的长度为2比A的长度大,那么B就是C的父节点. 由此规则建树,从叶子节点到根,父节点的价值=父节点本身的价值+孩子节点的价值。 求最后各个名字的价值

Input

 一个整数T,代表数据组数
对于每一组数据输入第一行为一个整数N(0

Output

 输出N个对应的名字的价值,按照输入的顺序输出(操作完成后最终价值)

Sample Input

1
3
a ab abc
10 20 30

Sample Output

60 50 30

Hint

 大数据输入,建议用scanf

Source

gyx