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
cohr3141592654:
20190411 20:41:55
AC in 1 go ezz segment tree


campha10x:
20190404 10:55:18
if this problem quite hard, you can check out the hint: https://spojsolution.github.io/2019/03/31/ADACLEAN.html 

aditya12legend:
20180528 19:24:09
@morass


codexter:
20180225 14:07:58
Can you please check 21232915. It exceeds time limit. Maybe some problem with hash function. I self reviewed many times, cant find mistake.


snitesh24:
20180103 00:04:46
@morass: I am getting WA , could you tell me where the code is failing id =20889399 

lalit_nit:
20171016 07:41:05
1 am getting TLE can anyone tell me expected TC 

starbot:
20170929 20:19:40
thanks morass...I was missing one memset statement....did it with sa.... 

morass:
20170929 13:26:17
@starbot: Good day to you, try following testcase:


starbot:
20170928 22:27:55
@Morass could you tell me where I am failing


Avik Sarkar:
20170815 09:45:54
AC in 1 GO ... Nice Hashing Problem . ... 
Added by:  Morass 
Date:  20160906 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 