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
techmint:
20210106 18:04:09
HINT: Use prime number 2^{63}  1 and modular multiplication if you want to use string hashing. 

sangmai:
20201029 11:54:06
cost me 12 WAs with 12 different hashing schemes to get to the correct one. 

misho8845:
20201014 00:47:12
To avoid WA use two hash functions!!! 

kungfupanda199:
20200920 06:15:23
Use mod value as 1e18+9 to avoid WA Last edit: 20200920 06:21:26 

chandanag23:
20200817 09:16:22
AC in one go. 

juanestebancg:
20200616 16:55:58
how to use two hash functions in this problem? 

dmj_specter07:
20200419 08:56:56
@akashbhalotia: I used the same hash functions as specified by you. But I am getting a WA. can you help me out?


icegambit91:
20200414 14:08:53
Never mind. I got it. 

icegambit91:
20200414 13:45:48
I used two hash functions and yet am continuously getting a WA verdict on test 13. Could someone please tell me why this may be happening? 

likhon5:
20200130 16:17:26
use two hash function to avoid collision Last edit: 20200130 16:19:56 
Added by:  Morass 
Date:  20160906 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 