Forgetful Waiter

Bob is a waiter at Pizza Round, a restaurant that serves many kinds of pizza on round tables of different sizes. When a group of customers arrives, Bob seats them at a table of the right size, takes their orders, and later serves the pizzas by placing them in front of the customers so that each customer receives the type of pizza they ordered.

Unfortunately, Bob is forgetful and cannot remember what each customer ordered, so he usually puts the pizzas down in the wrong places. The customers kindly cooperate, passing the pizzas around the table over several turns until everyone has the right one. In each turn, a customer may pick up a pizza in front of them with their left hand and pass it to the neighbor on their left, and/or pick up a pizza with their right hand and pass it to the neighbor on their right (both hands may be used in the same turn). At most 5 pizzas may sit in front of any customer at once, so a pizza can be passed to a neighbor only when that neighbor still has room.

Given the type each customer ordered and the type currently in front of each customer, find the minimum number of turns needed until every customer has the pizza they ordered. This is always possible: for each type, the number of pizzas of that type on the table equals the number ordered. Only the minimum number of turns matters, not the exact passing strategy.

For example, six customers sit around a round table; the label on each customer is the type they ordered, and the number on each pizza is its type. The pizzas can be delivered in two turns, but not in one, because the single type-2 pizza needs at least two turns to reach its destination.

Write a program that computes the minimum number of turns needed to bring every pizza on the table to the customer who ordered it.

The input contains several test cases. Each test case begins with a line holding an integer $n$, the number of customers in the group ($1 < n \le 1000$). The customers are numbered from $1$ to $n$ and sit around the table in counter-clockwise order, so customer $1$ is adjacent to customer $n$. Each of the next $n$ lines describes one customer: line $i$ contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), where $a_i$ is the pizza type customer $i$ ordered and $b_i$ is the pizza type currently placed in front of customer $i$. The sequence $b_1, \dots, b_n$ is a permutation of $a_1, \dots, a_n$. A line containing a single $0$ terminates the input.

For each test case, print a single line containing one non-negative integer: the minimum number of turns required to bring every pizza to the customer who ordered it. If the pizzas are already placed correctly, print $0$.