Matching Words

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int col = s.nextInt();
        s.nextLine();
        for (int i = 0; i < col; i++) {

            System.out.print(lampa(s.nextLine()) + " ");
        }

        s.close();


    }


    private static int lampa(String str) {
        int a = 0;
        Stack st = new Stack();
        for (int i = 0; i < str.length(); i++)
            switch (str.charAt(i)) {
                case '(': {
                    st.push(1);
                    break;
                }
                case ')': {
                    if (!st.empty() && Integer.parseInt(st.peek().toString()) == 1)
                        st.pop();
                    else return 0;
                    break;
                }
                case '[': {
                    st.push(2);
                    break;
                }
                case ']': {
                    if (!st.empty() && Integer.parseInt(st.peek().toString()) == 2)
                        st.pop();
                    else return 0;
                    break;
                }
                case '<': {
                    st.push(3);
                    break;
                }
                case '>': {
                    if (!st.empty() && Integer.parseInt(st.peek().toString()) == 3)
                        st.pop();
                    else return 0;
                    break;
                }
                case '{': {
                    st.push(4);
                    break;
                }
                case '}': {
                    if (!st.empty() && Integer.parseInt(st.peek().toString()) == 4)
                        st.pop();
                    else return 0;
                    break;
                }
            }
        if (st.empty())
            return 1;
        else return 0;
    }
}