Problem Statement

There are N baseball teams.
K belongs to team number 0.

All teams will play a round-robin tournament.
In the round-robin, all teams play 1 game against each other.
Every game has a definite winner and loser, and there are no draws.

Ranks are determined starting from 1st place, in descending order of the number of wins.
Teams with the same number of wins share the same rank, so multiple teams may have the same rank.
Also, ranks are determined starting from 1st place, and no number is skipped.

For example, even if 2 teams are in 1st place, the next rank is 2nd place.
The next rank does not become 3rd place just because 2 teams are in 1st place.
You are given the current table of wins and losses.
If there are remaining games, consider the patterns of wins and losses for those remaining games.
Answer the best rank that K's team, team 0, can possibly achieve.

Input

N
\(s_{0,0}\,s_{0,1}\,\dots s_{0,n-1}\)
\(s_{1,0}\,s_{1,1}\,\dots s_{1,n-1}\)
\(          \dots                  \)
\(s_{n-1,0}\,s_{n-1,1}\,\dots\,s_{n-1,n-1}\)

$ 2 \le N \le 6$ ($N$ is an integer)
si,j represents the result of the game of team i against team j.
'o' means a win, 'x' means a loss, and '-' means the game has not been played yet.
A match of a team against itself is represented by '#'.
The results of K's team, team 0, are in the first row of the table.
The table contains no impossible results, such as both teams winning.

Output

Ans

Output Ans, the best rank of team 0.
Do not forget to print a newline after the answer.

Sample

2
#-
-#

1

2
#x
o#

2

3
#xx
o#-
o-#

3

4
#-xx
-#x-
oo#-
o--#

2