There is a community of art lovers who meet from time to time and trade images with each other. Each image transaction must obey the following rules:

• The price at which the image is sold must be greater than or equal to the price at which it was bought.
• No trader is allowed to buy the same image more than once.

A new image has just appeared on the market. Trader 0 bought it from an unknown artist for the price of 0, and he is now ready to trade it among his fellow art lovers. You are given the prices, at which traders can buy the image at each other. Assuming all transactions obey the rules mentioned above, determine the longest possible sequence of transactions involving the new image. After all the transactions are done, print the number of people who have owned the image at some point in time, including both the final owner and trader 0.

Input

Consists of multiple test cases, each test has the following description. The first line contains the number of image traders n (2 ≤ n ≤ 15). Each of the next n lines contains n digits. They describe the price matrix, where the j-th character of the i-th line is a digit representing the price at which trader j will buy the image from trader i. It is known that 0 is the lowest price, and 9 is the highest.

Output

For each tests case determine the longest possible sequence of transactions involving the new image and print the number of people who have owned the image at some point in time, including both the final owner and trader 0. The answers for each test case print in a separate line.