정삼각형 도미노

보통의 도미노는 세로가 가로보다 두 배 긴 직사각형 타일이며, 두 정사각형 끝면에는 각각 $1$부터 $6$까지의 수가 눈금으로 표시되어 있습니다. 도미노 놀이는 서로 맞닿는 끝면의 수가 같도록 타일을 이어 놓는 방식으로 진행됩니다.

이번에는 도미노를 정삼각형으로 만들어 본다고 합시다.

정삼각형 도미노는 두 개의 정삼각형을 한 변끼리 붙여 만든 사각형(마름모)입니다. 마찬가지로 양쪽 끝의 삼각형에는 각각 $1$부터 $6$까지의 수가 적혀 있습니다. 두 정삼각형 도미노는 맞닿는 변의 양쪽 삼각형 끝에 적힌 수가 서로 같을 때에만 나란히 놓을 수 있으며, 어떤 도미노도 다른 도미노와 겹칠 수 없습니다. 첫 번째 도미노를 놓은 뒤에는, 새로 놓는 도미노를 반드시 이미 놓인 도미노 중 적어도 하나와 변을 맞대도록 놓아야 합니다. 즉, 놓인 도미노들은 항상 하나로 이어진 덩어리를 이루어야 하며, 서로 떨어진 두 개 이상의 덩어리는 올바른 배치가 아닙니다. 예를 들어 정삼각형 도미노를 다음과 같이 놓을 수 있습니다.

두 도미노가 맞닿아 공유하는 변 하나마다 $1$점을 얻습니다. 주어진 정삼각형 도미노 집합에 대하여, 올바른 배치로 얻을 수 있는 최고 점수를 구하세요. 집합의 모든 도미노를 반드시 사용할 필요는 없습니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 정삼각형 도미노의 개수를 나타내는 정수 $N$ ($1 \le N \le 6$)이 주어집니다. 이어지는 $N$개의 줄에는 각각 $1$ 이상 $6$ 이하의 두 정수가 주어지며, 이는 한 도미노에 적힌 두 눈금 값을 나타냅니다. 입력의 끝에는 $0$ 하나만 있는 줄이 주어지며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 주어진 정삼각형 도미노 집합으로 얻을 수 있는 최고 배치 점수를 한 줄에 출력합니다. 어떤 도미노도 다른 도미노와 나란히 놓을 수 없어 점수를 얻는 배치가 없다면 $0$을 출력합니다.