You are given a tree consisting of N vertices, rooted at vertex 1. Each vertex consists of a lowercase English alphabet as a node value.

If the ancestor node has the same node value as that of any vertex, then that ancestor node is considered as its valid parent vertex.

Your task is to detach all the nodes from the tree and attach them to any of the valid parent vertices (in the initial tree) and print the number of connected components obtained.

Input format

First line: An integer T denoting the number of test cases
Next line: An integer N denoting the number of nodes in the tree
Next line: N lowercase English alphabets such as Val₁, Val₂ , Val₃ ....Val_N, where Val_i denotes the node value of the \(i^{th}\) node
Next N-1 lines: Two integers U_i and V_i representing an edge between the nodes U_i and V_i

Output format

For each test case, print a single integer M in a new line representing the number of connected components formed after recreating the tree.

Constraints

\(1 \le T \le 10\)

\(1 \le N \le 10^5\)

\(a \le Val_i \le z\)

\(1 \le U_i , V_i \le N, U_i!=V_i\)

It is guaranteed that the given input forms a tree.