题目背景

小 M 迷上了画画，所以她用红色和黑色的画笔画出了一棵红黑树。

题目描述

这棵树有 $n$ 个点，从 $1$ 开始标号，其中 $1$ 号点为树根。一开始，小 M 给这 $n$ 个点分别涂上了红色或黑色，第 $i$ 号点的颜色是 $a_i$（'R' 代表红色，'B' 代表黑色）。

但可惜的是，小 M 对这棵树并不是非常满意，她希望第 $i$ 号点的颜色为 $b_i$。

好在她的好朋友小 K 懂得一点点膜法。小 K 可以先选定一个点，然后把这个点的颜色反转（红变黑，黑变红）。但这个膜法太强大了，所以会把膜法传递下去，即在反转的一秒之后使当前点的父节点颜色也进行反转，如此传递，直到根节点为止。特殊的，如果在同一时刻有多个膜法作用在同一个点上，这些膜法会两两抵消，如果恰好抵消完了（即膜法的个数为偶数），则当前点不会变色，并且不会有膜法继续传递下去。注意此处抵消膜法不需要耗时间。

但毕竟小 K 还是个新手，所以他在一秒之内只能最多对一个节点施展上述膜法。

为了尽快让小 M 开心，小 K 想知道，至少经过多少秒才能让这棵红黑树初次出现小 M 的理想颜色状态？可以证明，总可以按题目要求变成理想颜色状态。

输入格式

本题多测。

第一行一个整数 $Q$，表示数据组数。

对于每组数据：

第一行一个整数 $n$，表示红黑树的节点数。

第二行一个长度为 $n$ 的字符串 $a$，表示红黑树的初始颜色状态，其中仅含有 'R' 或 'B'。

接下来 $n-1$ 行，每行两个整数 $x,y$，描述一条树边。

最后一行一个长度为 $n$ 的字符串 $b$，表示红黑树的理想颜色状态，其中仅含有 'R' 或 'B'。

输出格式

共 $Q$ 行每行一个整数，一组数据一行，表示答案，即最小耗时。

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

提示

【样例解释】

第一组数据中，小 K 可以在第 $1$ 秒给 $4$ 号点膜法，整个树变为 RRBRR，在第 $2$ 秒给 $5$ 号点膜法，整个树变成 RBBRB，在第 $3$ 秒给 $1$ 号点膜法，整个树变成 BRBRB。

第二组数据中，小 K 可以在第 $1$ 秒给 $5$ 号点膜法，在第二秒给 $2$ 号点膜法；或者在第 $1$ 秒给 $3$ 号点膜法，在第 $2$ 秒给 $5$ 号点膜法。

【数据范围】

对于 $10\%$ 的数据，$1\leq n\leq 5$；

对于 $30\%$ 的数据，$1\leq n\leq 10$；

对于另外 $20\%$ 的数据，$\forall a_i\neq b_i$；

对于 $100\%$ 的数据，$1\leq n\leq 20$，$1\leq Q\leq 20$，树随机生成。