Considering N expressions of length n made up solely of the characters ) and (, give the number of parentheses to change to make the expression correctly parenthesized. Else, return -1

Input

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

Output

N lines

Examples

Input :

())()))

Output :

-1

Input :

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

**Output : **

3

Input :

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

Output :

5