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 .
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
No editorial available for this problem.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor