Two fighters were fighting in the arena to win the title HEAVY WEIGHT CHAMPIONSHIP and the special guest for the tournament was gennady korotkevich . After seeing for while our guest Mr. gennady got bored and decided to change the competition style, instead of fighting he gave them a string which may contains all integers from 0-9. now he is keen on knowing that how many sub-string that can be created from a given string contains a character c exactly p times.
As one of the fighter is from INDIA , so it becomes our national duty to solve this problem as quickly as possible to help INDIA win world heavy weight championship.
Input
First line contains integer t denoting the number of test cases,
for next 2*t (2 lines for each test case ) ,
the first line contain two integers p and c, second line contain a string.
Output
Output the answer in each line.
Constraints
1<=t<=10
i<=p,|s|<=1000000
0<=c<=9
For First testcases :
{1},{1,2},{2,3},{3}
that is {2},{2,1},{1,2},{2} are the sub strings that contains 2 exactly 1 time.
For Second testcases :
{1,2,3,4} , {2,3,4,5}
that is {5,5,5,5} , {5,5,5,5} are the sub strings that contains 5 exactly 4 times .
