Heavy Chain Clusterization

A group of biologists is looking for a cure for a viral disease. They tested many antibodies of different origins against the viral antigens and kept the $n$ antibodies that worked best in their experiments.

Every antibody is identified by its heavy chain, a sequence of amino acids. One amino acid is written as one uppercase English letter.

A set of antibodies is a similarity cluster when at least one of the following holds:

• the $k$-prefixes (the first $k$ amino acids) of all their heavy chains are equal;
• the $k$-suffixes (the last $k$ amino acids) of all their heavy chains are equal.

A set that holds a single antibody is always a similarity cluster.

To make the later research simpler, the biologists want to split the $n$ antibodies into similarity clusters, and every antibody has to belong to exactly one cluster. Find how few clusters are enough.

The first line contains two integers $n$ and $k$, the number of heavy chains and the length of the amino acid sequence that has to coincide ($1 \le n \le 5000$, $1 \le k \le 550$).

Each of the next $n$ lines contains the heavy chain of one antibody. Every amino acid is an uppercase English letter, and every heavy chain has at least $k$ and at most $550$ amino acids.

Print one integer, the minimum number of similarity clusters the $n$ antibodies can be split into.