건망증이 심한 웨이터

밥(Bob)은 여러 종류의 피자를 파는 식당 '피자 라운드(Pizza Round)'의 웨이터입니다. 이 식당의 탁자는 모두 크기가 제각각인 원형 탁자입니다. 손님 무리가 들어오면 밥은 알맞은 크기의 탁자로 안내하고 주문을 받은 뒤, 각 손님이 자신이 주문한 종류의 피자를 받도록 피자를 손님 앞에 놓아 줍니다.

그런데 밥은 건망증이 심해서 어느 손님이 무엇을 주문했는지 잘 기억하지 못하고, 그래서 대개 피자를 엉뚱한 자리에 놓고 맙니다. 다행히 손님들은 서로 협력하여 여러 차례에 걸쳐 피자를 올바른 사람에게 전달합니다. 한 차례(turn)에 각 손님은 자기 앞에 있는 피자를 왼손으로 집어 왼쪽 이웃에게 건네거나, 오른손으로 집어 오른쪽 이웃에게 건넬 수 있습니다. 두 손을 동시에 써서 한 차례에 양쪽 이웃에게 한 판씩 건넬 수도 있습니다. 다만 한 손님 앞에는 피자를 최대 5판까지만 둘 수 있으므로, 이웃 앞에 자리가 남아 있을 때에만 그 이웃에게 피자를 건넬 수 있습니다.

각 손님이 주문한 피자 종류와 현재 각 손님 앞에 놓인 피자 종류가 주어질 때, 모든 손님이 자신이 주문한 종류의 피자를 받기까지 필요한 최소 차례 수를 구하세요. 이것은 항상 가능함이 보장됩니다. 즉, 탁자 위에 있는 각 종류의 피자 개수는 그 종류를 주문한 손님 수와 정확히 같습니다. 우리가 관심 있는 것은 구체적인 전달 방법이 아니라 오직 최소 차례 수뿐입니다.

예를 들어 여섯 명의 손님이 원형 탁자에 둘러앉아 있고, 각 손님에 적힌 번호는 그 손님이 주문한 피자 종류를, 각 피자에 적힌 번호는 그 피자의 종류를 나타냅니다. 아래 그림처럼 피자는 두 차례 만에 전달할 수 있지만 한 차례로는 불가능합니다. 종류가 2인 피자 한 판이 목적지까지 가는 데 적어도 두 차례가 필요하기 때문입니다.

탁자 위의 모든 피자를 주문한 손님에게 전달하는 데 필요한 최소 차례 수를 구하는 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 손님 수를 나타내는 정수 $n$이 주어집니다 ($1 < n \le 1000$). 손님에게는 $1$번부터 $n$번까지 번호가 매겨져 있으며, 반시계 방향으로 차례대로 탁자에 둘러앉아 있으므로 $1$번 손님은 $n$번 손님과 이웃합니다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 두 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어집니다 ($1 \le a_i, b_i \le n$). 여기서 $a_i$는 $i$번 손님이 주문한 피자 종류이고, $b_i$는 현재 $i$번 손님 앞에 놓인 피자 종류입니다. 수열 $b_1, \dots, b_n$은 수열 $a_1, \dots, a_n$의 순열입니다. 입력의 끝은 $0$ 하나만 있는 줄로 표시됩니다.

각 테스트 케이스마다 한 줄에 음이 아닌 정수 하나를 출력하세요. 이는 모든 피자를 주문한 손님에게 전달하는 데 필요한 최소 차례 수입니다. 피자가 이미 올바르게 놓여 있다면 $0$을 출력합니다.