I. Палиндромные пары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Узнав много нового об освоении космоса, маленькая девочка по имени Ана хочет сменить тему исследования.

Ана это девушка, которая любит палиндромы (строки, которые читаются одинаково слева-направо и справа-налево). Она научилась проверять данную строку на палиндромность, но вскоре ей надоела эта задача, она придумала более интересную и теперь ей нужна ваша помощь, чтобы ее решить:

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

Две пары строк считаются разными, если строки находятся на разных позициях. Пара строк $$$(i,j)$$$ считается совпадающей с парой $$$(j,i)$$$.

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

В первой строке входного файла записано целое число $$$N$$$ ($$$1 \le N \le 100\,000$$$), обозначающее длину данного массива.

Следующие $$$N$$$ строк содержат по одной строке (состоящей только из латинских строчных букв от «a» до «z») — элементу исходного массива.

Суммарное количество символов во всех строках в массиве не превосходит $$$1\,000\,000$$$.

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

Выведите одно целое число, описывающее сколько палиндромных пар есть в этом массиве.

Примеры
Входные данные
3
aa
bb
cd
Выходные данные
1
Входные данные
6
aab
abcac
dffe
ed
aa
aade
Выходные данные
6
Примечание

Первый пример:

  1. aa $$$+$$$ bb $$$\to$$$ abba.

Второй пример:

  1. aab $$$+$$$ abcac $$$=$$$ aababcac $$$\to$$$ aabccbaa
  2. aab $$$+$$$ aa $$$=$$$ aabaa
  3. abcac $$$+$$$ aa $$$=$$$ abcacaa $$$\to$$$ aacbcaa
  4. dffe $$$+$$$ ed $$$=$$$ dffeed $$$\to$$$ fdeedf
  5. dffe $$$+$$$ aade $$$=$$$ dffeaade $$$\to$$$ adfaafde
  6. ed $$$+$$$ aade $$$=$$$ edaade $$$\to$$$ aeddea