A student has found a string of parentheses. They know that a correct parenthesis sequence is defined as follows:

• () is a correct parenthesis sequence.
• If $S$ is a correct parenthesis sequence, then $(S)$ is also a correct parenthesis sequence.
• If $S$ and $T$ are correct parenthesis sequences, then $TS$, which is obtained by concatenating the two strings, is also a correct parenthesis sequence.

Furthermore, a cyclic shift of size $k$ on a string $S$ results in a string $T$ such that: $\forall 0 \le i < |S|, T[i] = S[(i + k) \pmod{|S|}]$

The student's happiness is equal to the number of $k$ values smaller than the length of the input string such that the cyclic shift of the string by size $k$ is a correct parenthesis sequence. Find this number and report it to the student so they become happy.

Input

The first line of the input contains the integer $n$, which is the length of the string. The second line of the input contains the string $S$ consisting of the characters '(' and ')'.

Output

In the only line of output, print the student's happiness, which is equivalent to the number of cyclic shifts of the string that are correct parenthesis sequences.

Constraints

• $1 \le n \le 10^5$

Examples

Input 1

6
))()((

Output 1

2

Input 2

6
())(((

Output 2

0