Description

This tree has $n$ nodes, numbered from $1$, where node $1$ is the root. At the beginning, Little M colors each of the $n$ nodes either red or black. The color of node $i$ is $a_i$ ('R' means red, 'B' means black).

But unfortunately, Little M is not very satisfied with this tree. She wants the color of node $i$ to be $b_i$.

Luckily, her good friend Little K knows a little bit of "magic" (mo fa). Little K can first choose a node and then flip the color of that node (red becomes black, black becomes red). But this magic is too powerful, so it will be passed upward: one second after flipping the current node, the color of its parent node will also be flipped, and so on, until the root. Specially, if at the same moment multiple magic effects act on the same node, these magic effects cancel each other out pairwise. If they cancel out completely (i.e. the number of magic effects is even), then the current node will not change color, and no magic will continue to be passed upward. Note that canceling magic here does not take time.

However, Little K is still a beginner, so within one second he can cast the above magic on at most one node.

To make Little M happy as soon as possible, Little K wants to know: at least how many seconds are needed for this red-black tree to first reach Little M's desired color state? It can be proven that it is always possible to reach the desired color state as required.

Input Format

This problem has multiple test cases.

The first line contains an integer $Q$, which is the number of test cases.

For each test case:

The first line contains an integer $n$, the number of nodes in the red-black tree.

The second line contains a string $a$ of length $n$, describing the initial color state of the red-black tree, consisting only of 'R' or 'B'.

The next $n - 1$ lines each contain two integers $x, y$, describing an edge of the tree.

The last line contains a string $b$ of length $n$, describing the desired color state of the red-black tree, consisting only of 'R' or 'B'.

Output Format

Output $Q$ lines, each containing one integer. For each test case, output the answer, i.e. the minimum time cost.

2
5
RRBBR
1 2
1 3
2 4
2 5
BRBRB
5
RRRRR
1 2
2 3
3 4
4 5
BBBBB

3
3

Hint

[Sample Explanation]

In the first test case, Little K can cast magic on node $4$ in the $1$st second, and the whole tree becomes RRBRR; cast magic on node $5$ in the $2$nd second, and the whole tree becomes RBBRB; cast magic on node $1$ in the $3$rd second, and the whole tree becomes BRBRB.

In the second test case, Little K can cast magic on node $5$ in the $1$st second and on node $2$ in the $2$nd second; or cast magic on node $3$ in the $1$st second and on node $5$ in the $2$nd second.

[Constraints]

For $10\%$ of the testdata, $1 \le n \le 5$.

For $30\%$ of the testdata, $1 \le n \le 10$.

For another $20\%$ of the testdata, $\forall a_i \neq b_i$.

For $100\%$ of the testdata, $1 \le n \le 20$, $1 \le Q \le 20$, and the tree is randomly generated.

Translated by ChatGPT 5