beecrowd | 2585

Incomplete Dominoes

By Ricardo Martins, IFSULDEMINAS BR Brazil

Timelimit: 1

Caco lived boasting in the village, since it had a game of dominos greater than the conventional ones. Instead of the traditional 28 pieces, numbered from 0 to 6 at their ends, there were no repeated pieces, his had 55 pieces, numbered from 0 to 9 at their ends, and there were no repeated pieces. One day, Caco loaned his Domino to Chagas, and the same Would return, after a while, with missing parts. Before returning, Chagas wanted to analyze how much the Domino was still playable, even missing pieces. Given the remaining pieces, he wanted to see which sequence of pieces he could put on the table.

For example: If he had only four pieces remaining, and these pieces were 1-2, 2-2, 2-3, 4-4, as pictured below, the largest possible sequence would consist of three pieces:

Domino

Write a program that, given the remaining parts of the domino, reports the size of the largest possible sequence among them.

Input

There will be several test cases. Each test case will have an N number, with the total of remaining pieces. Then there will be N lines, with two integers, A and B (0 ≥ AB ≥ 9), indicating the numbers that are at the ends of the part. Tests end with end of file.

Output

Print the size of the largest possible sequence, relative to the parts of that test case.

Input Sample Output Sample

2
1 2
2 3
2
1 2
3 4
3
1 3
3 4
4 5

2
1
3