Hẳn bạn đã từng nghe nói đến trò chơi "Oẳn tù tì" (Rock, Paper, Scissors). Đàn bò thích chơi một trò tương tự mà chúng gọi là "Móng guốc, Giấy, Kéo" (Hoof, Paper, Scissors).

Luật chơi "Móng guốc, Giấy, Kéo" rất đơn giản. Hai con bò đấu với nhau. Cả hai cùng đếm đến ba, rồi đồng thời ra một cử chỉ tượng trưng cho móng guốc, một tờ giấy hoặc một chiếc kéo. Móng guốc thắng kéo (vì móng guốc có thể đập nát kéo), kéo thắng giấy (vì kéo có thể cắt giấy), còn giấy thắng móng guốc (vì móng guốc có thể bị giấy cứa). Chẳng hạn, nếu con bò thứ nhất ra cử chỉ "móng guốc" và con thứ hai ra "giấy", con bò thứ hai sẽ thắng. Tất nhiên, hai bên cũng có thể hòa nếu cùng ra một cử chỉ.

Farmer John thích thú theo dõi hai con bò chơi một loạt \(N\) ván "Móng guốc, Giấy, Kéo" (\(1 \leq N \leq 100\)). Đáng tiếc là dù có thể thấy đàn bò ra ba loại cử chỉ khác nhau, ông không phân biệt được cử chỉ nào là "móng guốc", cử chỉ nào là "giấy" và cử chỉ nào là "kéo" (dưới con mắt thiếu kinh nghiệm của Farmer John, tất cả dường như chỉ là những biến thể của "móng guốc"...).

Vì không biết ý nghĩa của ba cử chỉ, Farmer John gán cho chúng các số \(1\), \(2\) và \(3\). Có thể cử chỉ \(1\) là "móng guốc", nhưng cũng có thể là "giấy"; ông không thể biết chắc. Dựa trên các cử chỉ mà hai con bò đã ra trong cả \(N\) ván, hãy giúp Farmer John xác định số ván lớn nhất mà con bò thứ nhất có thể đã thắng, ứng với một cách ánh xạ phù hợp từ các số sang ba cử chỉ tương ứng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng còn lại chứa hai số nguyên (mỗi số là \(1\), \(2\) hoặc \(3\)), mô tả một ván đấu theo cách quan sát của Farmer John.

Dữ liệu ra

In số ván lớn nhất mà con bò thứ nhất trong hai con có thể đã thắng.

Ví dụ

5
1 2
2 2
1 3
1 1
3 2

2

Nguồn

USACO 2017 January Contest, Bronze — Hoof, Paper, Scissors. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=688