Étant donnée N expressions de longueurs n composées uniquement des caractères ) et (, donner le nombre de parenthèses à changer pour rendre l’expression correctement parenthésée. Sinon, renvoyer -1

Input

• 500 ≤ N ≤ 1000
• 5 ≤ n ≤ 500

Output

N lignes

Exemples

Input :

())()))

Output :

-1

Input :

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

**Output : **

3

Input :

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

Output :

5