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

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

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

6B. Distinct Deletions

Constraints

Input

Output

Samples

6B. Distinct Deletions

Constraints

Input

Output

Samples