LAZ has a tree of N nodes numbered from 1 to N, each node i contains a lowercase letter c(i). Let(a, b) represent a path from node a to node b,
then we can get a string S(a,b) consisting of letters along the shortest path. For example, if (a1, a4) = a1‐>a2‐>a3‐>a4, then the string we get is S(a1,a4) =c(a1)c(a2)c(a3)c(a4).
We define the value of (a, b) as F(S(a,b)), the length of (a, b) as L(a,b) which equals the number of edges in the path , and the ith node appearing in the path as
P(a,b,i), (i = 0,1, …, L(a,b)), then:
Now please count how many (a, b) in the given tree satisfies L(a,b) = X, F(S(a,b)) = Y.
Input
The first line contains a single integer T indicating the number of test cases.
In each of the following T test cases:
The first line contains three integers N, X, Y. (0<N<=50000, 0<=X, Y<2*10^9)
The second line contains N lowercase letters c(1), c(2), …, c(N).
Then N – 1 lines follows, each line contains two integers ui, vi representing an edge between ui
and vi.
Output
For each test case, output one line containing the number of (a, b) that satisfies L(a, b) = X,
F(S(a,b)) = Y.
Sample Input
1
4 2 33853
a a a a
1 2
1 3
1 4
Sample Output
6
Hint
The 6 paths are (2,3) (2,4) (3,2) (3,4) (4,2) (4,3).