make perfect open end parentheses

t = int(input())
for _ in range(t):
    s = input().strip()
    stack = []
    match = {')': '(', ']': '[', '}': '{'}
    valid = True
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack[-1] != match[char]:
                valid = False
                break
            stack.pop()
    if stack:
        valid = False
    print("True" if valid else "False")