H. The Great Hall
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After finally replacing his old MacBook with a gaming laptop, Tomeh has become addicted to video games, just as everyone expected.

He is currently playing The Great Hall. The game is represented by a string $$$t$$$ and consists of $$$k$$$ consecutive stages.

At the end of the $$$i$$$-th stage ($$$1 \le i \le k$$$), Tomeh encounters the boss of that stage. To let him pass, the boss gives him exactly one of the following choices:

  • Pay exactly $$$i$$$ gold coins.
  • Present any palindromic substring of string $$$t$$$ whose length is exactly $$$i$$$.

As a true "Shami", Tomeh will not spend a single coin unless he is absolutely forced to.

You are given a string $$$s$$$, an integer $$$k$$$, and $$$q$$$ queries.

Each query consists of two integers $$$l$$$ and $$$r$$$. Let $$$t = s[l \dots r]$$$ denote the corresponding substring of $$$s$$$.

For each query, determine the minimum total number of gold coins Tomeh must pay to clear all $$$k$$$ stages of the game played on the string $$$t$$$.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of test cases.

For each test case:

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le K \le N \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$ and the number of stages.

The second line contains a string $$$s$$$ of length $$$N$$$, consisting of lowercase English letters.

The third line contains an integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le N$$$), describing the substring $$$t = s[l \dots r]$$$.

It is guaranteed that:

  • The sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
  • The sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output

For each test case, print $$$q$$$ lines. For each query, output a single integer — the minimum total number of gold coins Tomeh must pay to clear all $$$K$$$ stages when the game is played on the string $$$t$$$.

Example
Input
2
9 5
abcbaffff
2
1 9
1 5
12 8
fbcaaaaacbef
2
3 10
4 7
Output
0
6
14
26