Problem Description

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.

Input

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'.

Output

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).

2
2 1
1 2 a
a
b
4 2
1 2 a
2 3 b
3 4 a
aa
ab

Case #1: 2
Case #2: 2

Hint

Please use #pragma comment(linker, "/STACK:16777216")