Distinct Deletions - Repovive Premier Round 3 | Repovive

6B. Distinct Deletions

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

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

6B. Distinct Deletions

Constraints

Input

Output

Samples

6B. Distinct Deletions

Constraints

Input

Output

Samples