In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

Every sequence of small letters and (also the empty sequence) is called an ab-word. If is an ab-word and are integers such that then denotes the subword of consisting of the letters . We say that an ab-word is nice if it has as many letters as and for all the subword has at least as many letters as .

Now, we give the inductive definition of the similarity between nice ab-words:

- every two empty ab-words (i.e. words with no letters) are similar;
- two non-empty nice ab-words and are similar
if they have the same length () and one of the following conditions if fulfilled:
- , and and are similar ab-words and they are both nice,
- there exists , , such that , are nice ab-words and
- , are nice ab-words and is similar to and is similar to , or
- , are nice ab-words and is similar to and is similar to .

A level of diversity of a non-empty set of nice ab-words is the maximal number of ab-words that can be chosen from in such a way that for each pair of chosen words, is not similar to .

Write a program that:

- reads elements of from the standard input;
- computes the level of diversity of the set ;
- writes the result to the standard output.

In the first line of the standard input there is a number of elements of the set , ; in the following lines there are elements of the set , i.e. nice ab-words (one word in each line); the first letter of every ab-word is the first symbol in line and there are no spaces between two consecutive letters in the word; the length of every ab-word is an integer from the range .

In the first and only line of the standard output there should be written one integer — the level of diversity of .

For the input data:

3 aabaabbbab abababaabb abaaabbabb

the correct result is:

2

*Task author: Krzysztof Diks.*