311307: CF1968G1. Division + LCP (easy version)

G1. Division + LCP (easy version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. In this version $l=r$.

You are given a string $s$. For a fixed $k$, consider a division of $s$ into exactly $k$ continuous substrings $w_1,\dots,w_k$. Let $f_k$ be the maximal possible $LCP(w_1,\dots,w_k)$ among all divisions.

$LCP(w_1,\dots,w_m)$ is the length of the Longest Common Prefix of the strings $w_1,\dots,w_m$.

For example, if $s=abababcab$ and $k=4$, a possible division is $\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$. The $LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$ is $2$, since $ab$ is the Longest Common Prefix of those four strings. Note that each substring consists of a continuous segment of characters and each character belongs to exactly one substring.

Your task is to find $f_l,f_{l+1},\dots,f_r$. In this version $l=r$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$, $l$, $r$ ($1 \le l = r \le n \le 2 \cdot 10^5$) — the length of the string and the given range.

The second line of each test case contains string $s$ of length $n$, all characters are lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output $r-l+1$ values: $f_l,\dots,f_r$.

ExampleInput

7
3 3 3
aba
3 3 3
aaa
7 2 2
abacaba
9 4 4
abababcab
10 1 1
codeforces
9 3 3
abafababa
5 3 3
zpozp

Output

0
1
3
2
10
2
0

Note

In the first sample $n=k$, so the only division of $aba$ is $\color{red}a\color{blue}b\color{orange}a$. The answer is zero, because those strings do not have a common prefix.

In the second sample, the only division is $\color{red}a\color{blue}a\color{orange}a$. Their longest common prefix is one.

题目大意：
这是一个关于字符串的问题。给定一个字符串s，对于固定的k，考虑将s划分为恰好k个连续的子字符串w1, ..., wk。定义fk为所有划分中LCP(w1, ..., wk)的最大可能值。LCP(w1, ..., wm)是指字符串w1, ..., wm的最长公共前缀的长度。任务是在l=r的条件下找出fl, f_{l+1}, ..., fr的值。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含三个整数n, l, r（1≤l=r≤n≤2×10^5），分别表示字符串的长度和给定的范围。
- 每个测试用例的第二行包含一个长度为n的字符串s，所有字符都是小写英文字母。
- 保证所有测试用例的n之和不超过2×10^5。

输出：
- 对于每个测试用例，输出r-l+1个值：fl, ..., fr。

示例：
输入：
```
7
3 3 3
aba
3 3 3
aaa
7 2 2
abacaba
9 4 4
abababcab
10 1 1
codeforces
9 3 3
abafababa
5 3 3
zpozp
```
输出：
```
0
1
3
2
10
2
0
```题目大意： 这是一个关于字符串的问题。给定一个字符串s，对于固定的k，考虑将s划分为恰好k个连续的子字符串w1, ..., wk。定义fk为所有划分中LCP(w1, ..., wk)的最大可能值。LCP(w1, ..., wm)是指字符串w1, ..., wm的最长公共前缀的长度。任务是在l=r的条件下找出fl, f_{l+1}, ..., fr的值。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含三个整数n, l, r（1≤l=r≤n≤2×10^5），分别表示字符串的长度和给定的范围。 - 每个测试用例的第二行包含一个长度为n的字符串s，所有字符都是小写英文字母。 - 保证所有测试用例的n之和不超过2×10^5。 输出： - 对于每个测试用例，输出r-l+1个值：fl, ..., fr。 示例： 输入： ``` 7 3 3 3 aba 3 3 3 aaa 7 2 2 abacaba 9 4 4 abababcab 10 1 1 codeforces 9 3 3 abafababa 5 3 3 zpozp ``` 输出： ``` 0 1 3 2 10 2 0 ```