F. Jumping Man
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have a tree rooted at node $$$1$$$ with $$$n$$$ nodes. Each node has a lowercase English letter written on it.

For each integer $$$i$$$ from $$$1$$$ to $$$n$$$, please solve the following problem independently:

  • Consider the set of strings formed by the following process:
    • Choose any node $$$u$$$ that is in the subtree of $$$i$$$ as your starting location.
    • Repeat 0 or more times:
      • Suppose you are currently on node $$$x$$$. Select a node $$$v$$$ that is in the subtree$$$^{\text{∗}}$$$ of node $$$x$$$, but you may not choose $$$v=x$$$. Move to node $$$v$$$. This process can be terminated at any point.
    • The characters obtained from all nodes you passed through (in order) are concatenated to form a string.

    You performed the above process exactly once for every possible path. Two paths are considered different if one node is visited in one path but not another.

    Now, you have obtained many strings. You want to know the sum of the square of the number of occurrences for each type of string. Since this answer might be very large, output its value modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$A node $$$v$$$ is in another node $$$x$$$'s subtree if and only if the shortest path from node $$$1$$$ to node $$$v$$$ passes through node $$$x$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). The description of the test cases follows.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \le n \le 5000$$$).

The next line is a string of length $$$n$$$ containing only lowercase English letters, where the $$$i$$$-th character represents the letter on the $$$i$$$-th node.

This is followed by $$$n-1$$$ lines, each containing two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n, u \neq v$$$) representing an edge of the tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output $$$n$$$ numbers on a new line: the answer for $$$i=1,2,\ldots,n$$$, modulo $$$998\,244\,353$$$.

Example
Input
5
3
abb
1 2
1 3
2
aa
1 2
4
ccbb
1 2
2 3
2 4
4
aaaa
1 4
4 2
2 3
10
cacbcccbac
1 2
2 3
3 4
2 5
1 6
2 7
3 8
4 9
8 10
Output
9 1 1 
5 1 
29 9 1 1 
69 5 1 19 
185 65 19 3 1 1 1 3 1 1
Note

For the first test case:

  • For nodes $$$2$$$ and $$$3$$$, the only string that is possible to get from the process is b. Therefore, the answer is $$$1$$$ for both.
  • For node $$$1$$$, the possible strings are a, ab, ab, b, and b. Overall, a is obtainable in one way, while ab and b are obtainable in two ways. Therefore, the answer for node $$$1$$$ is $$$1^2+2^2+2^2=9$$$.

In the fourth test case, for node $$$1$$$, the possible strings are:

  • aaaa (obtainable $$$1$$$ way)
  • aaa (obtainable $$$4$$$ ways)
  • aa (obtainable $$$6$$$ ways)
  • a (obtainable $$$4$$$ ways)

Therefore, the answer for node $$$1$$$ is $$$1^2+4^2+6^2+4^2=69$$$.