#1777 매치되는 괄호 찾기

44  1 s   128 MB  

Description

 

수식이 주어질 때 같은 짝의 괄호의 위치(index)를 찾는 문제이다.
 
(a*(b+c)+d)
 
이 경우에는 3 과 7 , 0 과 10 이 한 쌍의 괄호이다.
 

Input

 

맨 처음 테스트 케이스의 수 T( 1 <= T <= 20 )가 주어진다.
각 테스트 케이스마다 수식이 주어진다. 입력되는 문자는 영어 소문자 및 +, -, /, *, (, ) 이다.
문자열의 길이는 50을 넘지 않는다.

Output

왼쪽에서 오른쪽을 가면서 먼저 짝이 맞는 (여는 괄호 위치, 닫는 괄호 위치) 순으로 출력하고, 짝이 맞지 않는 수식은 not match 를 출력한다.

Sample Input

Sample Output

1
(a*(b+c)+d)
3 7
0 10