All Tracks Algorithms String Algorithms String Searching Problem

String Fight
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

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

SAMPLE INPUT
2
1 2
212
4 5
55555
SAMPLE OUTPUT
4
2
Explanation

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 .

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications