Moshtak is a reporter of daily potato. He likes to play with names. Whenever he writes someone’s name in his paper, he changes it to his own will. Once he changed Priyoti’s name. Priyoti got very angry. She invites him to play a game of strings. If he loses the game he has to change his name to potato. The rule of the game is given below. Moshtak will be given a string S of lower case alphabets. Priyoti will make some queries. In each query moshtak will be given a character C and an integer X. He has to tell the number of palindromes which are substrings of S, starts and ends with C and each contains exactly X occurrences of C. Moshtak does not want to be a potato. Please help him to win the game. Input Input starts with T, the number of test cases to follow. First line of each test case is an integer N. In the next line will contain a string S, consist of N lower case characters. In the next line an integer Q is given which is the number of query. In the next line a string QS consisting of Q characters is given i-th character of QS will be the C in i-th query. In the next line Q integers separated by space is given. i-th integer will be the X in the i-th query. All the integers in input will fit into 32 bit signed integer. All the strings in input will contain only lowercase alphabets and 1≤T ≤20,1≤|S|≤100000,1≤Q≤100000 Output For each test case, print the test case number as given in the sample output. Then for each query output the number of palindromes which are substrings of S and starts and ends with C and each contains exactly X occurrences of C. Sample Input 1 8 abccbaab 6 abcabc 222113 Sample Output Case 1: 2 2 1 3 3 0