E. Спасти Нивен!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Morning desert sun horizon

Rise above the sands of time...

Fates Warning, «Exodus»

Преодолев, наконец, Подветренные Пустоши, Ори добрался до Развалин Ветров, дабы отыскать Сердце Леса! Однако древнее хранилище, содержащее этот бесценный свет Ивы, не желало открываться!

Ори очень этому удивился, но огонек объяснил ему: хитрые Горлеки решили наложить дополнительную защиту на хранилище.

Горлеки очень любили операцию «разворачивания строки». А еще они очень любили возрастающие подпоследовательности.

Пусть дана строка $$$s_1s_2s_3 \ldots s_n$$$. Тогда «разворачиванием» этой строки назовем последовательность строк $$$s_1$$$, $$$s_1 s_2$$$, ..., $$$s_1 s_2 \ldots s_n$$$, $$$s_2$$$, $$$s_2 s_3$$$, ..., $$$s_2 s_3 \ldots s_n$$$, $$$s_3$$$, $$$s_3 s_4$$$, ..., $$$s_{n-1} s_n$$$, $$$s_n$$$. Например, «разворачиванием» строки 'abcd' будет последовательность строк 'a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'.

Чтобы открыть древнее хранилище, Ори должен найти длину наибольшей возрастающей подпоследовательности «разворачивания» строки $$$s$$$. Здесь строки сравниваются лексикографически.

Помогите Ори справиться с этой задачей!

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

Каждый тест содержит несколько наборов входных данных.

В первой строке находится одно целое положительное число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Описание наборов входных данных приведено ниже.

В первой строке каждого набора входных данных находится одно целое положительное число $$$n$$$ ($$$1 \le n \le 5000$$$) — длина строки.

Во второй строке каждого набора входных данных находится непустая строка длины $$$n$$$, состоящая из строчных латинских букв.

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

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

Для каждого набора входных данных выведите в отдельной строке одно целое число — ответ на задачу.

Пример
Входные данные
7
5
acbac
8
acabacba
12
aaaaaaaaaaaa
10
abacabadac
8
dcbaabcd
3
cba
6
sparky
Выходные данные
9
17
12
29
14
3
9
Примечание

В первом наборе входных данных «разворачивание» строки выглядит так: 'a', 'ac', 'acb', 'acba', 'acbac', 'c', 'cb', 'cba', 'cbac', 'b', 'ba', 'bac', 'a', 'ac', 'c'. В качестве наибольшей возрастающей подпоследовательности можно выбрать, например, 'a', 'ac', 'acb', 'acba', 'acbac', 'b', 'ba', 'bac', 'c'.