[SWEA] 괄호 검사 (Python)

T = int(input())

for test_case in range(1, T + 1):
    sen = list(input())
    ans = 1
    check = []
    for i in sen :
        if i == '{' or i=='(' :
            check.append(i)
            
        elif i == ')' or i == '}':
            if check :
                a = check.pop()
                
                if i==')' and a !='(':
                    ans = 0
                    break
                    
                elif i=='}' and a != '{':
                    ans = 0
                    break
                    
            else :
                ans = 0
                break
    
    if check :
        ans = 0
    print('#{} {}'.format(test_case, ans))