尽管$Bessie$发现每串平衡的括号在美学上都令人愉悦，但她特别喜欢被她称为“完美平衡”的括号串，即由一串“（”后跟一串相同个数的“）”。 例如：

（（（（））））

一天在谷仓中行走时，$Bessie$在地面上发现了$N \times N$的马蹄铁网格，每个马蹄的方向都使其看起来像（或）。从该网格的左上角开始，$Bessie$想要四处走动以拾起马蹄铁，以便使她拾起的路径连线（马蹄弦）达到完美平衡。请帮助她计算出她可以获得的最长的完美平衡串的长度。在每个步骤中，$Bessie$均可向上，向下，向左或向右移动。她只能移动到包含马蹄铁的网格位置，并且在这样做时，她会拿起马蹄铁，这样她就无法再移回同一位置（因为现在缺少马蹄铁）。她首先在网格左上角捡起马蹄铁。$Bessie$只捡起形成完美平衡弦的一系列马蹄铁，因此她可能无法捡起网格中的所有马蹄铁。

输入格式

第$1$行：整数$N（2 \leq N \leq 5）$。

第$2 \dots N + 1$行：每行包含一串长度为$N$的括号。 这$N$行共同描述了一个$N \times N$的括号网格。

输出格式

$1$行，$Bessie$可以收集的最长的完美平衡的马蹄弦的长度。

样例

样例输入

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

样例输出

8

样例解释

这样走可以得到$8$个长度的完美平衡马蹄弦

1())
2)((
345(
876)

数据范围与提示

• 对于 $100 \\%$ 的数据，$2 \leq N \leq 5$。
• 时间限制：$1\mathrm{s}$
• 空间限制：$256\mathrm{MB}$

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载