#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/6/problems/b

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/6/problems/b

Repovive

Distinct Deletions - Repovive Premier Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

6B. Distinct Deletions

1000 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

You are given a string $s$ of length $n$ consisting of lowercase English letters, and an integer $k$ .

For each $i$ with $1 \le i \le n-k+1$ , erase the contiguous substring from position $i$ to position $i+k-1$ , and write down the resulting string.

After doing this for all possible values of $i$ , count how many distinct strings have been written.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le k < n$
$s$ consists of lowercase English letters
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

$t$

\left. \begin{array}{l} n \quad k \\ s \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

2 1
ab

Case 2

5 2
ababa

Case 3

5 3
abcde

Case 4

7 3
abacaba

Case 5

8 3
abcabcaa

Explanation

Case 1

Erasing the first character leaves b, and erasing the second character leaves a. These two strings are different.

Case 2

Every possible erasure leaves the string aba, so only one distinct string is written.

Case 3

The three resulting strings are de, ae, and ab. They are all different.

Case 4

All five possible erasures produce different strings.

Case 5

The first five erasures all produce abcaa. The last erasure produces abcab, so there are two distinct strings.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given a string $s$ of length $n$ consisting of lowercase English letters, and an integer $k$ .

For each $i$ with $1 \le i \le n-k+1$ , erase the contiguous substring from position $i$ to position $i+k-1$ , and write down the resulting string.

After doing this for all possible values of $i$ , count how many distinct strings have been written.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le k < n$
$s$ consists of lowercase English letters
The sum of $n$ over all test cases is at most $2 \times 10^5$

$t$

\left. \begin{array}{l} n \quad k \\ s \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t