Considering N expressions of length n made up solely of the characters ) and (, determine if they are valid or not.

Input

• 500 ≤ N ≤ 1000
• 2 ≤ n ≤ 100

Output

N lines of True and False

Examples

Input :

)()()(()())

Output :

False

Input :

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

**Output : **

True