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