Có \(n\) quân bài được đặt trên mặt bàn thành 1 dãy từ trái qua phải. Mỗi quân bài chứa 3 kí tự đôi một phân biệt.

Ta gọi độ tương thích của 2 lá bài là số lượng kí tự khác nhau xuất hiện trong cả 2 lá. Ví dụ:

- “ABC” và “ACD” có độ tương thích là 2

- “ABC” và “DFE” có độ tương thích là 0

Bạn muốn lấy đi một số lá bài. Điều kiện để lấy lá bài \(x\) là độ tương thích của lá bài kề trái \(x\) và lá bài kề phải \(x\) phải lớn hơn hoặc bằng 2. Sau khi lấy đi lá bài \(x\), 2 lá bài kề \(x\) trước đó trở thành kề với nhau.

Xác định số lượng lá bài tối đa bạn có thể lấy ra.

Lưu ý: các lá bài được xếp thành 1 dãy, nên lá bài đầu tiên và cuối cùng không được tính là kề nhau

Dữ liệu vào:

• Dòng đầu tiên : Số nguyên \(n\ (\ 0\ < \ n\ \leq \ 50)\)

• \(n\) dòng tiếp theo: Mỗi dòng chứa 1 xâu gồm 3 kí tự đôi một phân biệt

Kết quả: Ghi ra một số nguyên duy nhất là số lá bài lớn nhất có thể lấy ra.

Ví dụ:

Giải thích:

Cách lấy tối ưu trong cả 2 test ví dụ:

#1: lấy lá bài số 2

#2: lấy lá bài số 4 (theo đánh số ban đầu)

#3: lấy lá bài số 3