Image Traders#1527
There is a community of art lovers who buy and sell images to each other. Each sale of an image must obey the following rules:
The price at which the image is sold must be at least as large as the price at which it was bought.
No trader may buy the same image more than once.
A new image has entered the market, and trader has bought it for . Afterwards, this image is resold among the existing art lovers. You are given the possible prices at which each trader can buy the image from another. Assuming that all sales follow the above rules, find the maximum possible length of the resale sequence.
After all transactions are completed, print the number of people who have possessed the image at any time, including both the last owner and trader .
The input consists of multiple test cases, each in the following format. The first line contains the number of traders (2 \leq n \leq 15). Each of the next lines contains digits. These describe the price matrix, where the -th character of the -th line is the price at which trader will buy the image from trader . It is known that is the lowest price and is the highest.
For each test case, determine the maximum possible length of the resale sequence for the new image and output the number of people who have possessed the image at any point, including the last owner and trader . Print the answer for each test case on a separate line.
Example 1