BaoBao 在他的左口袋里发现了一个长度为 $n$ 的序列 $A = a_0, a_1, \dots, a_{n-1}$。该序列中的每个元素 $a_i$ 要么是左括号 '('，要么是右括号 ')'。由于 BaoBao 不喜欢短序列，他决定让这个序列变得无限长！

令 $b_i$ 表示无限括号序列 $B$ 中第 $i$ 个位置的元素。由于 $B$ 是一个无限序列，$i$ 可以是正数、零，甚至是负数！可以通过以下方程从 $A$ 导出 $B$：

$$ \begin{cases} b_i = a_i & \text{若 } 0 \le i < n \\ b_i = b_{i-n} & \text{若 } i \ge n \\ b_i = b_{i+n} & \text{若 } i < 0 \end{cases} $$

由于 BaoBao 很无聊，他还制作了一个生成器，从序列 $B$ 中生成无限多个括号序列！令 $B^k$ ($k \ge 1$) 为生成器生成的第 $k$ 个无限序列，$b^k_i$ 为序列 $B^k$ 中第 $i$ 个位置的元素。为了完整起见，定义 $B^0 = B$。可以通过以下方程从 $B^{k-1}$ 导出 $B^k$：

$$ \begin{cases} b^k_i = b^{k-1}_{i+1} & \text{若 } b^{k-1}_i = \text{'('} \\ b^k_i = b^{k-1}_{i-1} & \text{若 } b^{k-1}_i = \text{')'} \end{cases} $$

为了更深入地了解该序列，BaoBao 想要计算 $B^k$ 的连续子序列 $b^k_l, b^k_{l+1}, b^k_{l+2}, \dots, b^k_{r-1}, b^k_r$ 中左括号 '(' 的数量。请编写一个程序来帮助他计算答案。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个字符串 $s$ ($1 \le |s| \le 10^5, s_i \in \{\text{'('}, \text{')'}\}$)，表示序列 $A$。$s$ 中的第 $i$ 个字符 $s_i$ 表示 $a_{i-1}$ 的值。

第二行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示查询次数。

接下来的 $q$ 行，每行包含三个整数 $k, l$ 和 $r$ ($0 \le k \le 10^9, -10^9 \le l \le r \le 10^9$)，表示一个查询。

保证所有测试数据的 $|s|$ 之和以及 $q$ 之和均不超过 $10^6$。

输出格式

对于每个查询，输出一行，包含一个整数，表示 $B^k$ 的连续子序列 $b^k_l, b^k_{l+1}, b^k_{l+2}, \dots, b^k_{r-1}, b^k_r$ 中左括号 '(' 的数量。

样例

输入 1

3
(())
3
0 -3 2
1 -2 3
2 0 0
))()(
3
0 -3 4
2 1 3
3 -4 -1
))()(()(
4
1234 -5678 9012
123 -456 789
12 -34 56
1 -2 3

输出 1

3
3
0
4
1
1
7345
623
45
3

说明

在以下解释中，$b^k_0$ 的值以粗体斜体标记。

对于第一个样例测试数据，我们有 $B^0 = \dots(())( \textit{\textbf{(}} )(())\dots, B^1 = \dots()()( \textit{\textbf{)}} ()()()\dots$ 以及 $B^2 = \dots)()()( \textit{\textbf{)}} ()()(\dots$，因此答案分别为 3, 3 和 0。

对于第二个样例测试数据，我们有 $B^0 = \dots))()()) \textit{\textbf{(}} )())()( \dots, B^1 = \dots())()( \textit{\textbf{)}} )()())()\dots, B^2 = \dots())() \textit{\textbf{(}} )())()())( \dots$ 以及 $B^3 = \dots()())( \textit{\textbf{)}} )())()())\dots$，因此答案分别为 4, 1 和 1。