더블팰린드롬

종현은 알고리즘 과제로 팰린드롬을 공부하고 있다. 팰린드롬은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열이다. 예를 들어 'abba'와 'level'은 팰린드롬이고, 'abab'와 'abc'는 팰린드롬이 아니다.

종현은 팰린드롬을 살펴보다가 새로운 현상을 발견했다. 먼저 길이가 짝수인 문자열 $X$, $Y$를 고른다. 그다음 $X$를 길이가 같은 두 부분으로 나누어 $X\_1$, $X\_2$를 얻는다. 종현은 $X\_1$, $Y$, $X\_2$를 순서대로 이어 붙여 새로운 문자열 $Z$를 만든다. 이렇게 얻은 $Z$가 팰린드롬이면 종현은 $X$와 $Y$가 더블팰린드롬 현상을 일으킨다고 부르기로 했다.

길이가 짝수인 $N$개의 서로 다른 문자열 $s\_1$, $s\_2$, $\ldots$, $s\_N$이 주어질 때, $X=s\_i$와 $Y=s\_j$가 더블팰린드롬 현상을 일으키게 하는 순서쌍 $(i, j)$의 개수를 구하라.

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

두 번째 줄부터 $N$개의 줄에 걸쳐 길이가 짝수이고 알파벳 소문자로만 이루어진 문자열 $s\_1$, $s\_2$, $\ldots$, $s\_N$이 한 줄에 하나씩 주어진다.

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

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