Word Game

The chief editor of The Puzzler magazine plans to introduce new logic puzzles based on words. Given a vocabulary, starting word W1 and target word W2, both from the vocabulary, the reader has to find a sequence of transformations producing W2 from W1. Each transformation applied to a word consists of up to L single edit operations. Each edit operation can be chosen as any character deletion, insertion or rewriting by another character. The product of each transformation is always required to be a word in the vocabulary. For example, if L=1 and the vocabulary contains words

then 'post' can be transformed to 'house' using 3 transformations If L=2 and the vocabulary is then 'frog' can be transformed to 'rat' using 4 transformations The Puzzler is known for its high difficulty. The chief editor thus wishes to have assignments as difficult as possible.

The task

We say that a sequence of transformations producing W2 from W1 is optimal if there is not any shorter sequence producing W2 from W1. You are given a vocabulary and a bound on the number of single edit operations allowed per one transformation. To quantify how difficult assignments can be created, your task is to compute the maximum of lengths of all optimal sequences of transformations where the starting and target word can be chosen arbitrarily.

Input

The first line of the input contains two integers L, N separated by space. L is the maximal number of single edit operations allowed per one transformation. N is the number of words in the vocabulary. Next, there are N lines, each of them containing one word of the vocabulary. A word is a string having characters in the range 'a' - 'z'. The length of every word is at most 20 characters. The value of L does not exceed 5, the value of N does not exceed 5000.

Output

The output contains one text line with single integer representing the maximal length of optimal sequences of transformations.

Example 1

Input
1 5
hose
house
pause
host
post
Output
3
An optimal sequence of transformations of the maximal length is e.g. post → host → hose → house.

Example 2

Input
2 8
dog
rat
cat
frog
pig
bat
horse
cow
Output
4
An optimal sequence of transformations of the maximal length is e.g. frog → dog → cow → cat → rat.

Example 3

Input
3 12
january
february
march
april
may
june
july
august
september
october
november
december
Output
3
An optimal sequence of transformations of the maximal length is e.g. june → july → may → march.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set