Description

题面翻译

给你一个二叉树，有人想从 $1$ 节点开始走到叶子节点，行动方法如下：

1. 当前点类型为 $L$，走到左儿子；
2. 当前点类型为 $R$，走到右儿子；
3. 当前点类型为 $U$，走到父亲。

行动前你可以修改点的类型，问至少需要修改多少次才能使得这个人能走到叶节点。

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the number of vertices in a tree.

The second line of each test case contains a string $s$ of $n$ characters — characters are written on the vertices. It is guaranteed that $s$ consists only of characters 'U', 'L', and 'R'.

The $i$-th of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0 \le l_i, r_i \le n$) — indices of left and right child of the vertex $i$. If $l_i = 0$, it means that vertex $i$ does not have a left child. If $r_i = 0$, it means that vertex $i$ does not have a right child. It is guaranteed that this data describes a valid binary tree rooted at $1$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, output a single integer — the minimal number of operations Keksic needs to do to reach a leaf.

5
3
LRU
2 3
0 0
0 0
3
ULR
3 2
0 0
0 0
2
LU
0 2
0 0
4
RULR
3 0
0 0
0 4
2 0
7
LLRRRLU
5 2
3 6
0 0
7 0
4 0
0 0
0 0
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

0
1
1
3
1

Note

In the first test case, vertex $1$ has $2$ as its left child and $3$ as its right child. Vertices $2$ and $3$ do not have children and are therefore leaves. As 'L' is written on vertex $1$, Keksic will go to vertex $2$, therefore he has to do no operations.

In the second test case, vertex $1$ has $3$ as its left child and $2$ as its right child. Vertices $2$ and $3$ are leaves. As 'U' is written on vertex $1$, Keksic needs to change it to either 'L' or 'R' in order for him to reach a leaf.

In the third case, vertex $1$ has only a right child, which is vertex $2$. As 'L' is written on it, Keksic needs to change it to 'R', otherwise he would be stuck on vertex $1$.

In the fourth case, he can change $3$ characters so that letters on the vertices are "LURL", which makes him reach vertex $2$.

In the fifth case, there are $3$ leaves, $3$, $6$ and $7$. To reach either leaf $6$ or leaf $7$, he needs to change $2$ characters. However, if he changes character on vertex $1$ to 'R', he will reach leaf $3$, therefore the answer is $1$.

The initial tree in test case 5.