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.


First line contains T, number of test-cases.

Each test-case begins with N, K, 1 ≤ K ≤ N ≤ 105, 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 test-cases won't exceed 3*105


For each test-case, print the number of unique substrings of length K

Example Input

3 2
5 1
4 2
10 2
7 3

Example Output


hide comments
likhon5: 2020-01-30 16:17:26

use two hash function to avoid collision

Last edit: 2020-01-30 16:19:56
rajon68: 2019-11-09 06:31:57

I am getting WA on 13 .I used only one hash function.!!

sphere913: 2019-08-13 12:42:29

@Morass Nice Problem

Last edit: 2019-08-15 01:12:26
ujjwalmittal: 2019-07-03 10:57:09

how to do this question i am not able to do

julkas: 2019-06-17 13:56:05

@Morass Good application.

akashbhalotia: 2019-06-10 17:27:41

You can use more than 1 hash function to make it stronger and avoid WA. I used two hash functions:
1) p=31, m=1e9+9
2) p=53, m=1e9+7

and it worked.

sagsango: 2019-05-28 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: 2019-04-11 20:41:55

AC in 1 go ezz segment tree

campha10x: 2019-04-04 10:55:18

if this problem quite hard, you can check out the hint:

aditya12legend: 2018-05-28 19:24:09

Can you please check the solution 21741453 . It is showing TLE .
Can you please explain me the reason . Thank You .

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