当前没有测试数据。

题目描述

虽然Bessie的母牛发现每一串平衡的括号在美学上都令人愉悦，但她特别喜欢她称为“完美”平衡的弦乐——由一串‘(’后跟一串‘)’长度相同的弦组成。例如："(（（（（）））））"

有一天，在走进谷仓时，Bessie在地面上发现了一个 $N \times N$ 网格的马蹄铁，每个马蹄铁都被定向，看起来像是'('或')'。从这个网格的左上角开始，Bessie想要四处走动拾起马蹄铁，这样她拾起的绳子就完全平衡了。请帮助她计算她能获得的最长的完美平衡弦的长度。

在每一步中，Bessie都可以向上，向下，向左或向右移动。她只能移动到一个包含马蹄铁的网格位置，当她这样做时，她拿起马蹄铁，这样她就不能再回到同一个位置（因为它现在没有马蹄铁）。她首先在网格的左上角拾起马蹄铁。Bessie只拿起一系列形成完美平衡弦的马蹄铁，因此她可能无法拾取网格中的所有马蹄铁。

输入格式

第1行：整数 $N$ ($2 \leq N \leq 5$)。

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

输出格式

1行：Bessie可以收集的最长的完美平衡马蹄铁串的长度。如果Bessie无法收集任何平衡的马蹄铁串（例如，如果左上方是右括号），则输出0。

输入样例

2
()
)(

输出样例

2