n 人のプレイヤー P₁, ..., P_n がこの順番で時計回りに座って，ババ抜きに似たカードゲームを行う．

このゲームでは，1 から n までの各番号が書かれたカードを 2 枚ずつ使う．最初に各プレイヤーはカードを 2 枚持っている．

まず，同じ番号のカードを 2 枚持っているプレイヤーは，それらのカードを場に捨てる．もし万一全員がカードを捨ててしまったら，ここでゲームは終了する．そうでなければ，ゲームが終了するまで，以下の動作を繰り返し行う．これ以降，プレイヤー p に対して，「次のプレイヤー」は，その時点でまだ手札が 1 枚以上残っているプレイヤーのうち，時計回りの方向で p から一番近い者を意味する．

• 次のようにプレイヤー p を選ぶ，
  • 1 回目は P₁ を選ぶ．ただし，P₁ の手札が残っていなければ，P₁ の次のプレイヤーを選ぶ．
  • それ以降は，前の回で選ばれたプレイヤーの次のプレイヤーを選ぶ．
• p の次のプレイヤー p′ は，p の手札を見て，その中で最小の番号のカードを引く．
• p′ が同じ番号のカードを 2 枚持つようになった場合には，その 2 枚のカードを場に捨てる．この結果，すべてのプレイヤーのカードがなくなったら，ゲームは終了する．

図 B-1 は，Sample Input で 2 番目のデータセットにおける 3 人のプレイヤーの初期手札を示している．この直後に，P₁ は手札の 2 枚のカードを捨てる．1 回目の p は P₂ である．なぜならば，P₁ の手札は空になっているからだ．

図 B-2 は，Sample Input の最後のデータセットで，以下の動作が終わった後の 5 人のプレイヤーの手札を示している．

• P₁ がまず選ばれ，P₁ の次のプレイヤー（すなわち P₂）が P₁ の手札の中から最小の番号 1 のカードを引く．この回の終わりに，P₂ は 1, 3, 5 の番号の 3 枚のカードを持つ．
• P₃, P₄, P₅ がこの順番に同じカード（最初は P₁ の手札にあった番号 1 のカード）を引く．
• P₅ が，同じ番号 1 のカード 2 枚を捨てる．

この後，P₁ が P₅ の手札から唯一残ったカードを引き，このカードと自分の手札の中の同じ番号 2 のカードを捨てる．次に手札を引かれるのは，P₅ の次のプレイヤーであり，P₁ の手札は空になっているので，それは P₂ である．

同じプレイヤーが 2 回手札を引かれる間に，少なくとも 1 対のカードが捨てられるので，遅かれ早かれゲームは終わる． ババ抜きとは異なり，最後にカードは残らない．

全プレイヤーの最初の手札が与えられた時，ゲームが終了するまでに何回カードが引かれるかを求めるプログラムを作成せよ．

入力は複数のデータセットからなり，各データセットは次の形式で表される．

n
c_1,1 c_1,2
⋮
c_n,1 c_n,2

n はプレイヤーの人数を表す． n は，2 以上 1000 以下の整数である． c_i,1 と c_i,2 は P_i の最初の手札の 2 枚のカードの番号である (1 ≤ i ≤ n)．1 から n までの各整数が，c_1,1, c_1,2, ..., c_n,1, c_n,2 の中にちょうど 2 回ずつ現れる．

入力の終わりは，ゼロだけからなる行で表される．入力のサイズは 10000 行以下である．

各データセットについて，カードが引かれる回数を表す 1 つの整数からなる行を出力せよ．

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

0
2
3
14
8
8