When we write a program, the symbols "(" and ")" are used frequently. These two symbols always appear in pairs. Now, Brain would like to write a program to determine that these two symbols in a program are legal or not.

The followings are the rules of these two symbols. 

One "(" can be canceled by one ")".

Successive "(" or successive ")" cannot be canceled. 

The case where ")(" can not be canceled.

Please help Amy to write a program to determine a program is legal or not.

Input Format:

The input contains several test cases. The first line contains one integer n indicating the number of test cases. The next n lines will contain zero or more characters. Please see the sample input

Output Format:

For each test case, output “true” if the program is legal, otherwise output “false”.

Technical Specification 

0 ≤ n ≤ 20 

Each test case contains as least one character, and no more than 50 characters.

Sample Input

5

()

)(()))

( (())((()())())

(hi)

Sample Output

true

false

false

true

true