Largest Valid Subset of Employee IDs

Given a list of employee IDs, your task is to find the size of the largest subset where no two IDs differ by exactly one character. Two IDs are said to differ by exactly one character if they have the same length and differ in exactly one position. Formally, if we denote two IDs as \(s\) and \(t\) of length \(n\), they differ by exactly one character if:

\(\sum_{i=1}^{n} I(s_i \neq t_i) = 1\)

You need to choose the subset with the maximum number of IDs satisfying the above condition.

inputFormat

The first line contains a single integer (n) representing the number of employee IDs. Each of the next (n) lines contains a single string representing an employee ID. All IDs consist only of lowercase letters.

outputFormat

Output a single integer denoting the size of the largest valid subset of employee IDs where no two IDs differ by exactly one character.## sample

4
abc
abd
acc
add

2