Узнав много нового об освоении космоса, маленькая девочка по имени Ана хочет сменить тему исследования.
Ана это девушка, которая любит палиндромы (строки, которые читаются одинаково слева-направо и справа-налево). Она научилась проверять данную строку на палиндромность, но вскоре ей надоела эта задача, она придумала более интересную и теперь ей нужна ваша помощь, чтобы ее решить:
Дан массив строк, состоящих из строчных букв латинского алфавита. Ваша задача — найти сколько палиндромных пар в массиве. Палиндромная пара — это пара строк, такая, что выполняется следующее условие: по крайней мере одна перестановка букв в конкатенации двух строк является палиндромом. Другими словами, если у вас есть две строки, скажем, «aab» и «abcac», мы объединяем их в «aababcac», и должны проверить, существует ли такая перестановка букв этой новой строки, что получится палиндром (в этом случае можно переставить буквы так, чтобы получить «aabccbaa»).
Две пары строк считаются разными, если строки находятся на разных позициях. Пара строк \((i,j)\) считается совпадающей с парой \((j,i)\).