Assume that you are given the n numbers. Find the maximum length of number ordering such that the last digit of one number (a_n) is the same as the first digit of the next number (a_n+1). For example the following series complies the Linked Numbers property:

  12 235 514 

   12 235 415 

Question: You will be given n positive integer. By possible replacements, find the length of longest linked numbers.

Input specification
In the first line, you will be given a number: The number of numbers(n) 1 ≤ n ≤ 30. Then, in the following n lines, you will be given n integers which are between 0 and 12,000.

Output specification
Show the length of the longest linked list