Bi rất thích nhưng xâu chuỗi được gọi là cân bằng tuyệt đối – gồm một xâu dấu mở ngoặc đơn '(' và được theo sau bởi một xâu dấu đóng ngoặc đơn ')' với cùng một độ dài. Ví dụ: (((()))).

Cho một ma trận kích thước ~n \times n~ gồm chỉ hai ký tự là ')' và '('. Xuất phát từ ô trái trên của bảng, Bi muốn đi một vòng để nhặt những ký tự trong ma trận sao cho xâu mà Bi nhặt được là xâu dấu ngoặc cân bằng tuyệt đối.

Quy tắc đi ở mỗi bước ta có thể đi lên phía trên, dưới, trái, và phải. Ô nào đã đi qua thì không còn ký tự để nhặt nữa. Bi chỉ nhặt những ký tự để có thể tạo thành một xâu dấu ngoặc cân bằng tuyệt đối, nên có thể cô ta không thể nhặt hết được tất cả các ký tự trong ma trận.

Hãy lập trình giúp Bi đếm độ dài lớn nhất của xâu dấu ngoặc cân bằng tuyệt đối mà Bi có thể nhặt được.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~2 \le n \le 5~.

~n~ tiếp theo mỗi dòng chứa một xâu các dấu ngoặc có độ dài là ~n~.

Output

In ra độ dài lớn nhất của xâu dấu ngoặc cân bằng tuyệt đối cần tìm. Nếu Bi không thể nhặt được một xâu dấu ngoặc cân bằng tuyệt đối (nếu vị trí trái trên là một dấu ngoặc đơn đóng) thì in ra ~0~.

Samples

Sample Input 1

4 
(()) 
()(( 
(()( 
))))

Sample Output 1

8