SP66 CRSCNTRY - Cross-country

Agness, a student of computer science, is very keen on cross­country running, and she participates in races organised every Saturday in a big park. Each of the participants obtains a route card, which specifies a sequence of checkpoints, which they need to visit in the given order. Agness is a very atractive girl, and a number of male runners have asked her for a date. She would like to choose one of them during the race. Thus she invited all her admirers to the park on Saturday and let the race decide. The winner would be the one, who scores the maximum number of points. Agnes came up with the following rules: - a runner scores one point if he meets Agnes at the checkpoint, - if a runner scored a point at the checkpoint, then he cannot get another point unless he and Agnes move to the next checkpoints specified in their cards. - route specified by the card may cross the same checkpoint more than once, - each competitor must strictly follow race instructions written on his card.

There is one integer d in the first line of the input file, 1

The i-th line of the output file should contain one integer. That integer should equal the greatest number of times Tom is able to meet with Agnes for race cards given in the i-th data set.