一个学生发现了一个括号字符串。他知道合法的括号序列定义如下：

• () 是一个合法的括号序列。
• 如果 $S$ 是一个合法的括号序列，那么 $(S)$ 也是一个合法的括号序列。
• 如果 $S$ 和 $T$ 是合法的括号序列，那么将它们拼接在一起得到的 $TS$ 也是一个合法的括号序列。

此外，对字符串 $S$ 进行大小为 $k$ 的循环移位会得到字符串 $T$，满足： $$\forall 0 \le i < |S|, T[i] = S[(i + k) \pmod{|S|}]$$

学生的“快乐值”等于小于输入字符串长度的 $k$ 的数量，使得对字符串进行大小为 $k$ 的循环移位后得到的字符串是一个合法的括号序列。请计算并告诉学生这个数值，让他感到快乐。

输入格式

第一行包含一个整数 $n$，表示字符串的长度。第二行包含字符串 $S$，由字符 ( 和 ) 组成。

输出格式

在唯一的一行中输出学生的快乐值，即循环移位后为合法括号序列的次数。

数据范围

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

样例

输入 1

6
))()((

输出 1

2

输入 2

6
())(((

输出 2

0