Duplicate Problem Titles

In the problem bank there are \( n \) problems. Each problem has a title which is a string of length less than 10. Let the title have length \( k \). We define two problems to be duplicates if and only if they have at least \( \lceil \frac{k}{2} \rceil \) positions where the characters are identical. Given \( n \) problem titles, determine the number of pairs of problems that are duplicates.

Note: It is guaranteed that all titles have the same length.

Input Format: The first line contains the integer \( n \). Each of the following \( n \) lines contains a problem title.

Output Format: Print a single integer, the number of duplicate pairs.

Formula: Two titles with length \( k \) are considered duplicates if the number of positions \( i \) (where \( 1 \le i \le k \)) for which the characters match is at least \( \lceil \frac{k}{2} \rceil \).

inputFormat

The first line contains an integer \( n \) (\( n \ge 3 \)), representing the number of problems. The following \( n \) lines each contain a string of length less than 10 (all having the same length) representing a problem title.

outputFormat

Output a single integer representing the number of duplicate pairs among the \( n \) problem titles.

sample

3
abc
abd
bbc

2