You are given a tree which has n nodes, the root’s id is 1 and each node has an lowercase latter.

It is clear that we can get n roads from the root, each road forms a road string. Please calculate the number of different substrings in each road string.

Input starts with an integer T (T <= 20) denoting the number of test case.
For each test case, n (1 <= n <= 10000) is given.
Next n - 1 lines contain two integers u and v (1 <= u, v <= n), denoting an edge.
The next line contains a string whose length is equal to n, the ith letter is belong to the node whose id is i.

For each test case, output n lines, each line is the number of different substrings in this node’s road string.