75. Fishing Soldier

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 ≤ 105
- 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

 Added by: ahmed_aly Added at: 2014-04-27 04:51:55 UTC Time Limit: 3 seconds Partial score: No Source: ACM Jordanian Collegiate Programming Contest 2013