Étant donnée N expressions de longueurs n composées uniquement des caractères ) et (, dire si elles sont valides ou non.

Input

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

Output

N lignes de True et False

Exemples

Input :

)()()(()())

Output :

False

Input :

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

**Output : **

True