ADACLEAN – Ada and Spring Cleaning Solution

0
26
SPOJ Solution

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

Relate posts

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.