Генетический анализатор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Весельчак У в очередной раз разрабатывает коварный план по захвату Вселенной. На этот раз он решил использовать передовые технологии, а именно — биоинженерию. Он собирается создать особый вирус, который сможет заразить всех жителей Галактики.

С нуля создать смертоносный вирус — задача не из простых, поэтому Весельчак У решил скомбинировать два существующих вируса. В его распоряжении находятся полностью расшифрованные геномы $$$n$$$ различных вирусов.

Геном каждого вируса представлен в виде строки, состоящей из строчных латинских букв. Для создания нового супер-вируса У планирует взять два различных вируса с геномами $$$s_1$$$ и $$$s_2$$$ и использовать специальную функцию совместимости:

$$$ L(s_1, s_2) = \text{lcp}(s_1, \text{reverse}(s_2)) + \text{lcp}(\text{reverse}(s_1), s_2) $$$

где $$$\text{lcp}(x, y)$$$ — длина наибольшего общего префикса строк $$$x$$$ и $$$y$$$, а $$$\text{reverse}(s)$$$ — строка $$$s$$$, записанная в обратном порядке.

Крыс Глот куда-то пропал, и поэтому задача о поиске наилучшей комбинации вирусов легла на вас. Найдите пару с наибольшей совместимостью, а то сами знаете, что будет иначе.

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

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

Первая строка содержит целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вирусов.

Следующие $$$n$$$ строк содержат геномы вирусов — непустые строки, состоящие из строчных латинских букв. Гарантируется, что все геномы различны.

Суммарная длина всех геномов по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных в первой строке выведите максимальную найденную совместимость. В следующей строке выведите два различных целых числа $$$a$$$, $$$b$$$, такие что $$$L(s_a, s_b)$$$ — максимально. Если подходящих пар несколько, можно вывести любую.

Пример

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

    44aabcabcacbddcdaa2ab5abcdcacbcbacacddccac2cbb

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

    31 401 223 212 1