괄호 문자열은 다음과 같이 정의된다.</p>

1. 빈 문자열은 괄호 문자열이다.
2. S가 괄호 문자열일 때, (S)도 괄호 문자열이다.
3. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다.
4. 모든 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다.

'('와 ')'로 이루어진 문자열 S = s₁s₂...s_N과 M개의 쿼리가 주어진다. 각각의 쿼리는 l_i와 r_i(1 ≤ l_i ≤ r_i ≤ n)로 이루어져 있다. 각각의 쿼리에 대해서 다음을 구해야 한다.

• S의 부분 문자열 s_li, sli+1</sub>, ..., sri</sub>의 부분 수열 중에서 괄호 문자열이면서 가장 긴 것의 길이를 출력한다.</sub>

문자열 S = s₁s₂...s_N의 길이가 |x|인 부분 수열이란, 1 ≤ k₁ < k₂ < ..., K_|x| ≤ N을 만족하는 문자열 x = s_k1sk2</sub>...sk|x|</sub>를 의미한다.</sub>

입력 형식

첫째 줄에 문자열 S가 주어진다. (1 ≤ N ≤ 1,000,000)</p>

둘째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

셋째 줄부터 M개의 줄에 쿼리 l_i와 r_i가 주어진다.

출력 형식

각각의 쿼리마다 정답을 출력한다.

예제 입력

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

예제 출력

0
0
2
10
4
6
6