题目描述

Bessie特别喜欢"完美平衡"的括号字符串——由相同数量的连续'('和连续')'组成，例如：(((())))。

某天，Bessie在谷仓发现一个N×N的马蹄铁网格，每个马蹄铁方向看起来像'('或')'。从网格左上角出发，Bessie想通过移动收集马蹄铁，组成最长的完美平衡字符串。

移动规则：

• 每次可以向上、下、左、右移动
• 只能移动到有马蹄铁的格子，收集后该格子变为空
• 必须从左上角开始收集
• 收集的马蹄铁序列必须形成完美平衡字符串

输入格式

第一行：整数N（2 ≤ N ≤ 5）

接下来N行：每行一个长度为N的括号字符串，共同描述N×N网格

输出格式

一行：能收集的最长完美平衡字符串长度（若无法收集则输出0）

输入输出样例

输入 #1

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

输出 #1

8

样例解释

Bessie的移动路径：

1. 从左上角(1,1)开始收集'('
2. 向下到(2,1)收集'('
3. 向下到(3,1)收集'('
4. 向右到(3,2)收集'('
5. 向下到(4,2)收集')'
6. 向左到(4,1)收集')'
7. 向上到(3,1)已空
8. 向右到(3,3)收集')'
9. 向上到(2,3)收集')'

最终收集序列：(((())))（长度8）