D. Drone Kaleidoscope
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Welcome to the XVII Annual Drone Kaleidoscope (DK for short)! A one-lane track is written as a string $$$s$$$ of $$$n$$$ lowercase characters.

During the annual DK, several teams, one by one, perform a show as follow:

  • Each team picks a different palindrome that actually appears somewhere on the track.
  • Each team selects some subset of occurrences of their chosen palindrome, and places a drone in the leftmost character of the selected occurrences.
  • To avoid radio noise within the team performance, that team's drone starting positions must be at least $$$k$$$ characters apart.
  • Finally, the team flies their drones over the selected occurrences of the chosen palindrome.

A team's show value is $$$$$$ \text{(length of its palindrome)} \times \text{(number of drones it places)}. $$$$$$

Choose how many teams to field (each using a distinct palindrome) and, for each chosen team, pick the starting positions of its drones so as to maximize the total show value across all shows.

For example, if we have $$$s=abaaba$$$ and k=3, a valid show configuration is to field $$$3$$$ teams as follows:

  1. The first team chooses the palindrome $$$aba$$$ and launches $$$2$$$ drones with initial positions $$$\{1,4\}$$$. This team's show value is $$$3 \times 2=6$$$.
  2. The second team chooses the palindrome $$$baab$$$ and launches $$$1$$$ drones with initial position $$$\{2\}$$$. This team's show value is $$$4 \times 1=4$$$.
  3. The third team chooses the palindrome $$$a$$$ and launches $$$2$$$ drones with initial positions $$$\{1,6\}$$$. This team's show value is $$$1 \times 2=2$$$. Note that launching $$$3$$$ drones with initial positions $$$\{1,3,6\}$$$ is invalid, since starting positions should be at least $$$k=3$$$ characters apart.

The total show value in this example is $$$6+4+2=12$$$. Note that this is not the configuration that maximizes the total show value.

Input

Each test contains multiple test cases. The first line contains $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq n \leq 10^5$$$ and $$$1 \leq k \leq n$$$) — the length of string $$$s$$$ and the parameter $$$k$$$ described in the statements.

The following line contains a string $$$s$$$ of length $$$n$$$ consisting only of English lowercase characters.

The sum of $$$n$$$ over all test cases is guaranteed to be at most $$$10^5$$$.

Output

Print one integer for each test case — the maximum total show value you can achieve.

Example
Input
4
7 2
abacaba
7 4
abacaba
7 6
abacaba
6 3
abaaba
Output
28
26
22
22