After entering university, students face the task of choosing courses. There are $N$ students who need to choose courses, and there are three teachers in the school: JYY, YJY, and YYJ. In the first year, each student chose one of these teachers.

After a year of study, students have formed certain impressions of each other. Each student ranks the other $N-1$ students from best to worst based on their impressions. The second year of course selection begins, and each student needs to choose a teacher. Perhaps because they were "tricked" too much in the first year, every student wants to switch to a different teacher. You are asked to coordinate the students' course selections such that the "worst" impression among students attending the same class is as good as possible.

Input

The first line contains an integer $N$.

The next $N$ lines each contain $N$ positive integers. The $(i+1)$-th line provides information for the $i$-th student. The first integer $A_i$ is one of $0, 1, 2$, representing the teacher chosen by the $i$-th student in the first year. The following $N-1$ integers are a permutation of $1, 2, \dots, i-1, i+1, \dots, N$, representing the $i$-th student's ranking of other students from best to worst.

Output

Output a single integer, the minimum non-negative integer $T$ such that:

1. All students choose a teacher different from the one they chose in the first year.
2. For any two students who choose the same teacher, their impression of each other is among the top $T$ best.

See the examples for more details.

Constraints

• For 30% of the data, $N \le 20$.
• For 60% of the data, $N \le 100$.
• For 100% of the data, $N \le 1000$.

Examples

Input 1

6
0 2 3 4 5 6
0 1 3 4 5 6
1 6 5 4 2 1
2 6 5 3 2 1
1 1 2 3 4 6
2 1 2 3 4 5

Output 1

4

Input 2

3
0 2 3
1 1 3
2 1 2

Output 2

0

Note

For the first example, the six students choose teachers 1, 2, 0, 0, 2, and 0 respectively. In this case, the impression of student 4 by student 6 in teacher 0's class is the 4th best, so the answer $T$ is 4. It is impossible to find a smaller $T$.

For the second example, if all students are assigned to different classes, $T$ is 0.