가장 긴 도미노 사슬

도미노는 2x1 크기의 직사각형 타일로, 면이 두 칸으로 나뉘어 각 칸에 0부터 6까지의 점이 찍혀 있다. 많은 도미노 게임에서는 이웃한 두 도미노가 맞닿는 칸의 점 개수가 같도록 도미노를 한 줄로 길게 이어 붙인다.

완전한 도미노 한 세트에는 서로 다른 28개의 면이 있다: 0-0, 0-1, 0-2, 0-3, 0-4, 0-5, 0-6, 1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5, 3-6, 4-4, 4-5, 4-6, 5-5, 5-6, 6-6. 도미노는 양쪽 방향 어느 쪽으로도 놓을 수 있으므로 1-6 도미노는 1/6으로도 6/1로도 사용할 수 있다.

도미노 여러 개가 주어질 때(같은 면이 여러 번 나올 수도 있다), 하나의 사슬로 이어 붙일 수 있는 도미노의 최대 개수를 구하시오.

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝까지 계속된다.

각 테스트 케이스의 첫 줄에는 사용할 수 있는 도미노의 개수 N (1 <= N <= 1000)이 주어진다. 이어지는 N개의 줄에는 각각 0 이상 6 이하의 정수 두 개가 주어져 도미노 하나를 나타내며, 첫 번째 정수는 두 번째 정수보다 크지 않다.

각 테스트 케이스마다 이어 붙일 수 있는 가장 긴 사슬에 포함된 도미노의 개수를 한 줄에 하나씩 출력한다.