편자

소 베시는 균형 잡힌 괄호 문자열을 모두 좋아하지만, 그중에서도 완전 균형 문자열을 특히 좋아합니다. 완전 균형 문자열이란 여는 괄호 ( 가 연속으로 나온 뒤, 같은 개수의 닫는 괄호 ) 가 연속으로 나오는 문자열입니다. 예를 들면 다음과 같습니다.

(((())))

어느 날 베시는 외양간을 거닐다가 $N \times N$ 크기의 편자 격자를 발견했습니다. 각 편자는 ( 또는 ) 모양 중 하나로 놓여 있습니다. 베시는 왼쪽 위 칸에서 출발해 편자를 주우며 돌아다니면서, 주운 편자들이 이루는 문자열이 완전 균형이 되도록 하려고 합니다. 베시가 얻을 수 있는 가장 긴 완전 균형 문자열의 길이를 구하세요.

한 번에 베시는 상하좌우로 한 칸 이동할 수 있습니다. 편자가 아직 남아 있는 칸으로만 이동할 수 있으며, 그 칸으로 이동하면 편자를 줍기 때문에 그 칸은 비게 되어 다시는 돌아갈 수 없습니다. 베시는 항상 왼쪽 위 칸의 편자를 먼저 줍습니다. 베시는 완전 균형 문자열을 이루는 편자들만 가지므로, 격자의 모든 편자를 다 줍지 못할 수도 있습니다.

• 첫째 줄: 정수 $N$ ($2 \le N \le 5$).
• 둘째 줄부터 $N+1$째 줄까지: 각 줄에는 길이 $N$ 인 괄호 문자열이 주어집니다. 이 $N$ 개의 줄이 함께 $N \times N$ 격자를 나타냅니다.

• 첫째 줄: 베시가 모을 수 있는 가장 긴 완전 균형 편자 문자열의 길이. 어떤 균형 문자열도 모을 수 없다면 (예를 들어 왼쪽 위 칸이 ) 인 경우) 0 을 출력합니다.

아래 그림은 길이 8 의 완전 균형 문자열을 얻는 한 격자와 그 수집 순서를 함께 보여 줍니다. 각 숫자는 그 칸의 편자를 줍는 단계를 나타내며, 괄호가 그대로 남아 있는 칸은 방문하지 않은 칸입니다.

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

주운 편자를 단계 순서대로 읽으면 (((()))) 가 되며, 이는 완전 균형 문자열이고 길이는 8 입니다.