G1. Деление + LCP (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. В этой версии $$$l=r$$$.

Дана строка $$$s$$$. Для фиксированного $$$k$$$ рассмотрим деление $$$s$$$ на ровно $$$k$$$ непрерывных подстрок $$$w_1,\dots,w_k$$$. Пусть $$$f_k$$$ — максимально возможное $$$LCP(w_1,\dots,w_k)$$$ среди всех делений.

$$$LCP(w_1,\dots,w_m)$$$ — это длина самого длинного общего префикса строк $$$w_1,\dots,w_m$$$.

Например, если $$$s=abababcab$$$ и $$$k=4$$$, то возможное деление $$$\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$$$. $$$LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$$$ равно $$$2$$$, так как $$$ab$$$ — самый длинный общий префикс этих четырех строк. Обратите внимание, что каждая подстрока состоит из непрерывного сегмента символов, и каждый символ принадлежит ровно одной подстроке.

Ваша задача — найти $$$f_l,f_{l+1},\dots,f_r$$$. В этой версии $$$l=r$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого теста содержит три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le l = r \le n \le 2 \cdot 10^5$$$) — длина строки и заданный диапазон.

Вторая строка каждого набора содержит строку $$$s$$$ из $$$n$$$ символов, все символы — строчные буквы английского алфавита.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$r-l+1$$$ значений: $$$f_l,\dots,f_r$$$.

Пример
Входные данные
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
Примечание

В первом примере $$$n=k$$$, поэтому единственное деление $$$aba$$$ — $$$\color{red}a\color{blue}b\color{orange}a$$$. Ответ — ноль, потому что у этих строк нет общего префикса.

Во втором примере единственное деление — $$$\color{red}a\color{blue}a\color{orange}a$$$. Их самый длинный общий префикс равен одному.