Matt receives a gift from his friend Bobo. It is a tree which has N vertices and (N - 1) edges with single character. Yes, it is the tree in computer science.
Matt denotes the number of edges between vertices a and b as d(a, b). The string obtained by concatenating all characters from a to b is defined as s(a, b).
Given string L and R of length M, Matt would like to know the number of (a, b) s.t.
● d(a, b) = M,
● L<=s(a, b)<=R.
where "<=" means lexicographical comparision.
The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.
For each test case, the first line contains two integers N (2<=N<=10^5) and M (1<=M<N).
Each of the following (N - 1) lines contains a
i, b
i, c
i denoting an edge between vertex a
i and b
i with character c
i (1<=a
i, b
i<=n).The vertices are conveniently labled with 1, 2,……, n. c
i is either 'a' or 'b'.
The last two lines contain string L and R (|L| = |R| = M, L<=R). L and R consist of 'a' and 'b'.
For each test case, output one line "Case #x: y", where x is the case number (starting from 1), y is the number of (a, b).