There are n words of length m, consisting of characters a \dots z.

Uolevi will sort the words in lexicographical order. However, before this, he may choose one of the words and replace one of its letters with another letter from a \dots z.

Your task is to count the number of words that may become the first word in the list.

Input

The first line contains two integer n and m: the amount of words and the length of every word.

After this, n lines follow, each containing one word: a string of length m.

Output

Print the required number of words.

Constraints

• 1 \leq n \leq 10^{5}
• 1 \leq m \leq 10

Example

Input:

4 2
aa
bb
za
zz

Output:

3

Explanation:

• To make aa the first word, Uolevi doesn't need to do anything.
• To make bb the first word, Uolevi can replace the first a in aa with z.
• To make za the first word, Uolevi can replace the z with a (equivalent words can be in any order).
• Uolevi cannot make the word zz the first word.