Description

The baseball game of planet Pandora is similar to the game of the Earth. In the game field, there are four bases which are named “home base”, “first base”, “second base” and “third base”. At the beginning, nobody is on the bases. There are two teams, one is the attacking team, and the other is the defending team.

One by one, all players of the attacking team goes to the home base and bats the ball thrown by the defending team.

There are four possible results of a bat:

According to the rule, a player must leave the field immediately after he scores one point for his team. The game ends after every player of the attacking team has batted once(A “Sacrifice” is also regarded as a bat), or after there has been 3 batters who get an “Out” or an “Sacrifice”.

Avatar is the coach of an attacking team. He knows that the same player performs differently when the player takes different turns. For example, if you let Jack to be the first batter, he will definitely get an “Out”, but if you let him play in the third turn, he will get an “Allrun”. Avatar knows his men very well. He asked you to find out the best “batting order” for his team. If the team bats in that order, their score will be maximized.

Input

There are multiple test cases, ended by 0.

For each test case:

The first line contains an integer n（1 <= n <= 15）, meaning the number of players in Avatar’s team. All players are numbered for 1 to n.

Then a n×n matrix A follows. Aij describes what result the player i will get if he is the jth batter.( i and j start from 1 )

Following is the meaning of the value of Aij:

0 means the result is “Out”

1 means the result is “Sacrifice”

2 means the result is “Bingle”

3 means the result is “Allrun”

Output

For each test case, print one line containing the highest score Avatar’s team can get in the game.

5
0 2 0 1 2
1 0 2 0 2
0 2 1 2 0
0 2 2 1 2
2 1 0 2 0
0

2

Source

2010 National Programming Invitational Contest Host by ZSTU