Bông có \(n\) đoạn chuỗi hạt, mỗi đoạn chuỗi gồm một số hạt, các hạt có màu sắc khác nhau và được mô tả bằng các ký tự từ 0 đến 9. Bông muốn ghép các đoạn chuỗi hạt này thành một chuỗi vòng tròn theo quy tắc: đoạn chuỗi muốn ghép theo sau đoạn chuỗi \(S_i\) thì màu hạt cuối cùng của \(S_i\) phải giống với màu hạt đầu tiên của chuỗi tiếp theo. Tất nhiên, với một đoạn chuỗi hạt khi ghép vào chuỗi vòng tròn có thể lấy theo chiều xuôi hoặc chiều ngược. Sau khi suy nghĩ, Bông nhận thấy \(n\) đoạn chuỗi mà Bông có không thể ghép hết để thành một vòng tròn được. Do đó, Bông muốn tìm cách ghép để được chuỗi vòng tròn gồm nhiều đoạn chuỗi nhất.

Yêu cầu

Cho danh sách gồm \(n\) đoạn chuỗi, tìm cách chọn nhiều đoạn chuỗi nhất trong \(n\) đoạn chuỗi để ghép được thành một vòng tròn mà vòng tròn phải có ít nhất \(3\) đoạn.

Input

• Dòng đầu chứa số nguyên dương \(n\);
• Dòng thứ hai đến dòng thứ \(n+1\) mô tả \(n\) đoạn chuỗi, mỗi dòng là một xâu số có độ dài không vượt quá \(10\).

Output

• Gồm một dòng chứa một số là số lượng nhiều nhất chọn được để ghép được thành một vòng tròn mà vòng tròn phải có ít nhất \(3\) đoạn. Nếu không thể ghép được vòng tròn nào thỏa mãn, in ra \(0\).

Constraints

• \(n \leq 100\).
• Các ký tự trong xâu thuộc đoạn [0, 9].
• Độ dài mỗi xâu không quá \(10\).

Example

4
0
12
23
13

3

Scoring

• Có \(100\%\) số điểm tương ứng với các ràng buộc đã nêu.