32357번 - 더블팰린드롬

문제

종현은 알고리즘 과제로 팰린드롬에 대해서 공부하고 있다. 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열을 말한다. 예를 들어 'abba', 'level' 등은 팰린드롬이며 'abab', 'boj' 등은 팰린드롬이 아니다.

종현은 팰린드롬을 보다가 새로운 현상을 발견하게 되었다. 먼저, 길이가 짝수인 문자열 $X,ドル $Y$를 고른다. 그리고 $X$를 같은 길이의 두 부분으로 나누어 문자열 $X_1,ドル $X_2$를 얻는다. 다음으로 종현은 $X_1,ドル $Y$와 $X_2$를 순서대로 이어 붙여 새로운 문자열 $Z$를 얻는다. 이렇게 얻은 $Z$가 팰린드롬이라면 종현은 $X$와 $Y$가 더블팰린드롬 현상을 일으킨다고 부르기로 했다.

길이가 짝수인 $N$개의 서로 다른 문자열 $s_1,ドル $s_2,ドル $...,ドル $s_N$이 주어질 때, $X=s_i$와 $Y=s_j$가 더블팰린드롬 현상을 일으키게 하는 두 정수 $i,ドル$j$의 쌍 $(i,ドル $j)$의 개수를 구해보자.

입력

첫 번째 줄에 문자열의 개수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 길이가 짝수인 알파벳 소문자로만 구성된 문자열 $s_1,ドル $s_2,ドル $...,ドル $s_N$이 주어진다.

출력

더블팰린드롬 현상을 일으킬 수 있는 쌍의 개수를 출력한다.

제한

• 2ドル \le N \le 10,000円$
• 1ドル \le i \le N$
• 1ドル \le j \le N$
• $i \neq j$
• 입력으로 주어지는 모든 수는 정수이다.
• 입력으로 주어지는 문자열의 길이는 1ドル,000円$ 이하이며 짝수이다.
• 입력으로 주어지는 문자열은 중복되지 않는다.

힌트