## LCC/Moose '19 Contest 5 J5 - 4D Strings

View as PDF

Points: 15 (partial)
Time limit: 10.0s
Memory limit: 512M

Author:
Problem types

A string is considered a palindrome if it is the same forwards as it is backwards. For example, aa and racecar are palindromes, while abaa and hello are not.

A string considers a string a friend if the concatenation of and in that order results in a palindrome.

In addition, two strings and are close iff both of the following conditions are satisfied:

1. considers a friend or one the strings considers a friend is close with .
2. considers a friend or one the strings considers a friend is close with .

Given strings labelled , can you determine how many pairs of strings are close?

#### Input Specification

The first line will contain the integer .

The next line will contain space-separated strings . will only contain lowercase latin characters and will contain at least one character.

We guarantee that the sum of the string lengths do not exceed . In other words, .

#### Output Specification

Output one integer: the number of pairs of strings that are close. Note that this number may not fit in a 32-bit integer.

No further constraints.

#### Sample Input 1

4
abb a bba bbba

#### Sample Output 2

6