01204212/paren

from 01204212

You have a string consisting of parentheses ( ), curly braces { }, and brackets [ ]. You want to check if they are properly balanced. The following are examples of balanced strings:

(()())(())((())())
[()[]]
{[]}{[][](()[])}

These are unbalanced strings:

)(
[[))
[{]}
{{{{}}}}}

You want to write a program that performs the balance checking.

Input/Output

Input

The first line: an integer T, the number of test cases. The next T lines: each line contains a string representing each test case.

Output

For each test case, output either yes if the string is balanced, and no if the string is not balanced.

Example

Input

5
()()(())
((((
[[](){{}}]
[][][]()(){}
[[{]}]

Output

yes
no
yes
yes
no

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.process();
    }

    private void process() throws Exception {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        int t = Integer.parseInt(reader.readLine());
        
        for(int i=0; i<t; i++) {
            String st = reader.readLine(); 
            
            if(check(st)) {
                System.out.println("yes");
            } else {
                System.out.println("no");                
            }
        }
    }

    private boolean check(String st) {
        // ... your code here
    }
}