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