괄호 문자열

"괄호 문자열"은 우리가 흔히 사용하는 여섯 개의 괄호 기호들 ("(", ")", "[", "]", "{", "}")로만 구성된 문자열을 일컫는다.

그 중 "균형잡힌" 괄호 문자열은 아래 조건에 따라 정의된다.

1. "()" "[]" "{}" 이 셋은 균형잡힌 괄호 문자열이다.
2. 문자열 "X"와 "Y"가 균형잡힌 괄호 문자열이라면 "XY" 와 "YX"도 균형잡힌 괄호 문자열이다.
3. 문자열 "Z"가 균형잡힌 괄호 문자열이라면 앞/뒤로 "("과")" 혹은 "{"과"}" 혹은 "["과"]"을 붙인 문자열 "(Z)" 혹은 "{Z}" 혹은 "[Z]"도 균형잡힌 문자열이다.
4. 마지막으로, 편의상 길이가 0인 "" 문자열도 균형잡힌 괄호 문자열이다. (예제 참고)

예를 들어 "[](){}", "[[()]]", "{}[()]" 은 균형잡힌 괄호 문자열이고, "[][[", "()(}", "{]" 은 균형잡힌 괄호 문자열이 아니다.

우리가 다룰 문자열은 와일드카드 ("*")를 포함할 수 있는데, 각 와일드카드는 여섯 개의 괄호 기호 중 하나로 대체될 수 있다. 예를들어 S = "[**)" 라는 문자열을 생각해보자. 첫 번째 와일드카드를 "]"로 대체하고 두 번째 와일드카드를 "("로 대체하면 S' = "[]()" 라는 새로운 문자열을 얻을 수 있고, 이는 균형잡힌 괄호 문자열이다. 만약 첫 번째 와일드카드를 "("로 대체하고 두 번째 와일드카드를 "]"로 대체하면 바뀐 문자열은 S'' = "[(])"가 되고 이는 균형잡힌 괄호 문자열이 아니다.

상기한 괄호 기호와 와일드카드로만 구성된 문자열이 입력으로 주어졌을 때, 당신은 이 문자열을 (가능한 길이가 가장 긴) 균형잡힌 괄호 문자열로 바꾸고 싶다. 이를 위해 일부 문자는 지워야 할 수 있고, 각 와일드카드는 당신이 임의로 여섯 개의 괄호 기호 중 하나로 바꿀 수 있다 (혹은 필요 없다면 지울 수 있다). 예를 들어 입력 문자열이 A = "***" 인 경우를 생각해보자. 균형잡힌 괄호 문자열의 길이가 홀수일 수 없으므로 세 글자 중 한 글자를 지우고, 남은 두 개의 와일드카드는 "()" 혹은 "[]" 혹은 "{}"로 대체하여 길이가 2인 균형잡힌 괄호 문자열을 만들 수 있다.  다른 예로 B = "[{([" 인 경우 상기한 4번 조건에 해당하는 길이가 0인 균형잡힌 괄호 문자열을 얻을 수 있지만, 길이가 더 긴 균형잡힌 괄호 문자열을 얻는 것은 불가능하다. 마지막으로 C = "(]{}){([)}" 인 경우, 대괄호 기호 두 개 ("]"와 "[")를 제거하면 길이가 6인 균형잡힌 괄호 문자열 "({}){()}"을 얻을 수 있다. 

위와 같이 와일드카드와 여섯 개의 괄호 기호들로만 구성된 문자열이 입력으로 주어졌을 때, 가장 긴 균형잡힌 괄호 문자열을 얻기 위해 지워야 하는 문자의 (최소) 개수를 출력하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 줄에 문자열이 하나씩 주어진다.

각 테스트 케이스에 대하여 최소 몇 개의 문자를 지워 균형잡힌 괄호 문자열을 얻을 수 있는지 출력한다.

• 1 ≤ T ≤ 10
• 1 ≤ 문자열 길이 ≤ 500