Trên một bảng A kích thước ~n \times n~ với ~n~ là số lẻ, các ô trên bảng có thể chứa một trong ba ký tự: g, a,y.

Chúng ta định nghĩa các ô thuộc tập ~Y~ bao gồm các ô nằm trên:

• Đường chéo bắt đầu từ ô trên cùng bên trái và kết thúc tại ô trung tâm của bảng.
• Đường chéo bắt đầu từ ô trên cùng bên phải và kết thúc tại ô trung tâm của bảng.
• Đường thẳng đứng bắt đầu từ ô trung tâm,kéo thẳng xuống và kết thúc tại biên dưới của bảng.

Một bảng tồn tại ~Y-letter~ nếu và chỉ nếu:

• Các ô thuộc tập ~Y~ có cùng một ký tự.
• Các ô không thuộc tập ~Y~ có cùng một ký tự.
• Các ô thuộc tập ~Y~ và các ô không thuộc tập ~Y~ phải có ký tự khác nhau.

Bạn có một thao tác duy nhất là thay đổi ký tự của một ô thành một trong ba ký tự g, a, hoặc y.

Hãy xác định số thao tác ít nhất cần thực hiện để bảng có thể xuất hiện ~Y-letter~.

Input

Dòng đầu tiên là số nguyên ~n~ ~(1 \le n \le 10^3)~

~n~ dòng tiếp theo,mỗi dòng gồm ~n~ kí tự ~s_i~ ~(s_i \in \{'g','a','y'\})~

Output

Một dòng duy nhất là số thao tác ít nhất

Subtask

• Subtask 1 : Không có ràng buộc gì.

Sample Input

3
ayy
aag
gag

Sample Output

3

Giải thích

Ô tô màu xanh là những ô bị thay đổi