Problem Statement:

Khaled Sami is a competitive programmer and a student of coach Fegla. He graduated a year ago and he's now almost done with his military service. He was assigned to some top secret navy facility working as a fisherman.

The place he's fishing at has some peculiar properties:

- There is a maximum of 52 different kinds of fish, each represented by a unique upper or lower case English letter.

- We can think of any sea area as a single row of consecutive cells that is either occupied by a fish or not.

- All the fish in that specific area would be swimming next to each other in a single continuous block with no empty cells between any of them.

- If a fishing net is thrown, we can think of it as covering cells from i to j. In this case, all fish in cells i till j (including cells i and j) will be caught in the net.

Yesterday, Khaled's commanding officer discussed with him a new fishing strategy which is targeting a specific kind of fish with the goal of catching K fishes swimming in K consecutive cells. So Khaled wants to write a program that can calculate the number of ways that he can throw his net (the number of indices i,j where i ≤ j ) to catch at least K consecutive fish of a specific kind. Since he's out in the sea, he needs you to write the program for him.

Input Format:

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by T test cases, each test case begins by two lines, the first line contains a string of lowercase and uppercase English letters representing the fish in the sea (every letter is a single fish) and the second containing two integers, K and Q where K is the number described above and Q is the number of questions Khaled is going to ask. Q lines follow, each containing a single lowercase or uppercase English letter that he Khaled wants to find about. (1 ≤ Q ≤ 10)

Note that

- N, the number of fish in the string is constrained by 2 ≤ N ≤ 10^{5}

- K ≤ N

- the sea is considered to be fully occupied by fish, so Khaled can only throw his net on indices i,j where 1 ≤ i, j ≤ N, i ≤ j

Output Format:

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by Q lines, each containing a single integer denoting the number of ways Khaled can throw his net to catch at least K consecutive fishes of the respective type in the input.

Sample Input:

1
dfffaaafffaffff
3 2
f
a

Sample Output:

Case 1:
69
45