Z-Pipe Cat recommends you play Ballance. In the game, players control a ball that can change its material (i.e., physical properties) to navigate through a vast and complex maze made of paths and mechanisms, avoiding traps, using mechanisms, and solving puzzles to eventually reach the finish line.

The balance ball has 3 types of materials (paper, wood, stone). In the game, the ball needs to pass through $n$ mechanisms, and each mechanism only allows balls of certain materials to pass. Initially, you need to spend a cost of 1 unit to select a material for the ball. Before passing through each mechanism, you can spend a cost of 1 unit to switch the ball to another material, or you can keep the current material at no cost.

Now, you can arrange the order in which you pass through the mechanisms. Please find the minimum cost required for the ball to pass through these $n$ mechanisms.

Input

The first line contains an integer $n$ ($1 \le n \le 100$), representing the total number of mechanisms.

The next $n$ lines each contain three integers $a_{i,1}, a_{i,2}, a_{i,3}$ ($a_{i,1}, a_{i,2}, a_{i,3} \in \{0, 1\}$), where the $j$-th integer in the $i$-th line being 0 or 1 indicates that the $i$-th mechanism does not allow or allows the $j$-th material, respectively. It is guaranteed that $a_{i,1}, a_{i,2}, a_{i,3}$ are not all 0.

Output

An integer representing the minimum cost required to pass through these $n$ mechanisms by reasonably arranging the order of the mechanisms and the materials used.

Examples

Input 1

5
1 0 0
1 0 1
0 1 0
1 0 1
0 0 1

Output 1

3

Note

A reasonable arrangement of the mechanism order and material costs is as follows:

The order of passing through the mechanisms is the 3rd, 1st, 4th, 5th, and 2nd mechanisms as given in the input.

Initially, spend a cost of 1 unit to select the 2nd material for the ball. Before passing through the 3rd mechanism, keep the current material at no cost. Before passing through the 1st mechanism, spend a cost of 1 unit to switch the ball to the 1st material. Before passing through the 4th mechanism, spend a cost of 1 unit to switch the ball to the 3rd material. Before passing through the 5th mechanism, keep the current material at no cost. Before passing through the 2nd mechanism, keep the current material at no cost.

It can be proven that the minimum cost required to pass through these $n$ mechanisms with a reasonable arrangement of order and materials is 3.