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
rajon68:
20191109 06:31:57
I am getting WA on 13 .I used only one hash function.!! 

sphere913:
20190813 12:42:29
@Morass Nice Problem Last edit: 20190815 01:12:26 

ujjwalmittal:
20190703 10:57:09
how to do this question i am not able to do 

julkas:
20190617 13:56:05
@Morass Good application. 

akashbhalotia:
20190610 17:27:41
You can use more than 1 hash function to make it stronger and avoid WA. I used two hash functions:


sagsango:
20190528 13:32:35
. If the hashes are equal (hash(s)=hash(t)), then the strings do not necessarily have to be equal.Keep This in mind Good Luck. 

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.

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