Весельчак У в очередной раз разрабатывает коварный план по захвату Вселенной. На этот раз он решил использовать передовые технологии, а именно — биоинженерию. Он собирается создать особый вирус, который сможет заразить всех жителей Галактики.
С нуля создать смертоносный вирус — задача не из простых, поэтому Весельчак У решил скомбинировать два существующих вируса. В его распоряжении находятся полностью расшифрованные геномы $$$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
