Móng ngựa

Có lưới $N\times N$ gồm các dấu ngoặc ( và ). Bắt đầu từ góc trên trái, di chuyển lên/xuống/trái/phải (không ghé lại ô đã thăm), thu thập dấu ngoặc trên đường đi.

Tìm chuỗi dài nhất có dạng $k$ dấu ( theo sau là $k$ dấu ) (với $k\ge 1$) có thể thu thập được.

Dữ liệu vào

• Dòng $1$: Số nguyên $N$.
• $N$ dòng tiếp: Mỗi dòng $N$ ký tự ( hoặc ).

Dữ liệu ra

Một số nguyên — độ dài chuỗi dài nhất (0 nếu không thể).

Ràng buộc

• $2\le N\le 5$

Ví dụ