괄호

올바른 괄호 수열을 다음과 같이 귀납적으로 정의한다.

• 빈 수열은 올바른 괄호 수열이다.
• $s$가 올바른 괄호 수열이면 $(s)$와 $[s]$도 올바른 괄호 수열이다.
• $a$와 $b$가 올바른 괄호 수열이면 이 둘을 이어 붙인 $ab$도 올바른 괄호 수열이다.
• 위 규칙으로 만들 수 없는 수열은 올바른 괄호 수열이 아니다.

예를 들어 다음 수열은 모두 올바른 괄호 수열이다.

(), [], (()), ()[], ()[()]

반면 다음 수열은 올바른 괄호 수열이 아니다.

(, ], )(, ([)], ([(]

괄호 문자로 이루어진 수열 $a_1 a_2 \dots a_n$이 주어질 때, 이 수열의 부분수열 중 올바른 괄호 수열이 되는 가장 긴 것의 길이를 구하라. 즉, $1 \le i_1 < i_2 < \dots < i_m \le n$인 인덱스 $i_1, i_2, \dots, i_m$에 대하여 $a_{i_1} a_{i_2} \dots a_{i_m}$이 올바른 괄호 수열이 되는 가장 큰 $m$을 구하면 된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 문자 (, ), [, ]만으로 이루어진 한 줄이며, 각 줄의 길이는 $1$ 이상 $100$ 이하이다.

입력의 끝은 end라는 단어 하나만 있는 줄로 표시하며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 가장 긴 올바른 괄호 부분수열의 길이를 한 줄에 하나씩 출력한다.

수열 ([([]])]의 경우, 가장 긴 올바른 괄호 부분수열 중 하나는 [([])]이며 그 길이는 $6$이다.