ADACLEAN  Ada and Spring Cleaning
Ada the Ladybug has decided to do some "Spring Cleaning". As you might know, she keeps a TODO list. She is very sparing so she keeps all her activities as one string. You might get very confused while reading the string but she has a system  every activity has length exactly K characters. Sadly, as new activities were added to the list many duplicities appeared. Now it is time to find out how many unique activities are in her TODO list.
Input
First line contains T, number of testcases.
Each testcase begins with N, K, 1 ≤ K ≤ N ≤ 10^{5}, length of string and length of activites respectively.
Next line consists of string of length N, consisting of lowercase letters.
The sum of lengths of strings among all testcases won't exceed 3*10^{5}
Output
For each testcase, print the number of unique substrings of length K
Example Input
5 3 2 aaa 5 1 abcba 4 2 abac 10 2 abbaaaabba 7 3 dogodog
Example Output
1 3 3 4 4
hide comments
Palashvijay4O:
20161029 23:29:05
getting WA.. dont know what's the issue.


morass:
20161011 21:24:51
@asshole: Asctivities are not one after another  they overlap, so there are NK+1 activities in a string :) 

asshole:
20161011 19:43:25
I don't understand the question. since each activity is of k length shouldn't there the string length be multiple of k?


mehmetin:
20160911 16:19:23
Accepted with PYPY, but WA with C++14... 

Vipul Srivastava:
20160911 09:23:03
what is the expected complexity of the solution? 

it_is_me:
20160910 21:00:51
Getting WA constantly anybody can please provide me a good test case to check my solution.


aitya:
20160909 18:55:06
Finally AC. Brilliant test cases.Shows how a problem is only as good as it's test cases :) 

aditya730:
20160909 17:22:23
Last edit: 20160909 17:23:37 

morass:
20160909 16:20:10
@aitya: Hello, well I'm slightly afraid you are failing only "big" testcases :'( 

aitya:
20160909 14:53:48
i am constantly getting wa.Can you tell whether i am failing the most basic test cases or the corner ones

Added by:  Morass 
Date:  20160906 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 