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 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

Output

For each test-case, 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
sangmai: 2020-10-29 11:54:06

cost me 12 WAs with 12 different hashing schemes to get to the correct one.

misho8845: 2020-10-14 00:47:12

To avoid WA use two hash functions!!!

kungfupanda199: 2020-09-20 06:15:23

Use mod value as 1e18+9 to avoid WA

Last edit: 2020-09-20 06:21:26
chandanag23: 2020-08-17 09:16:22

AC in one go.

juanestebancg: 2020-06-16 16:55:58

how to use two hash functions in this problem?

dmj_specter07: 2020-04-19 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?
code link: http://p.ip.fi/foXr

icegambit91: 2020-04-14 14:08:53

Never mind. I got it.

icegambit91: 2020-04-14 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: 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.!!


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