Count Palindromic Concatenations

Little Johnny enjoys playing with words. He has chosen \( n \) palindromes and then generated all \( n^2 \) possible pairs by concatenating each pair of palindromes. Your task is to determine how many of the concatenated words are palindromes.

A string \( s \) is called a palindrome if it reads the same forwards and backwards, i.e. \( s = s^R \). Given that each individual word is already a palindrome, you must check for every pair \( (a, b) \) whether the concatenation \( a+b \) satisfies \( a+b=(a+b)^R \).

Input Format: The first line contains an integer \( n \). The following line (or \( n \) subsequent lines) contains \( n \) palindromic words separated by spaces or newlines.

Output Format: Output a single integer: the number of concatenated pairs that form a palindrome.

inputFormat

The input consists of:

1. An integer \( n \) representing the number of palindrome words.
2. \( n \) palindromic words separated by spaces and/or newlines.

outputFormat

Output a single integer, representing the count of pairs \( (a, b) \) (with repetition allowed) such that the concatenation \( a+b \) is a palindrome.

sample

3
a b c

3