One day while playing with parentheses '{' and '}' , Panda came across an interesting question , given a string A consisting of parentheses we've to perform the following operation: Given two integers L and R,find the length of correct parentheses subsequence.

Note: All the indices (L and R) for above operation are according to 1 indexed.

INPUT:
First line of input contains a string comprising of parentheses '{'and '}'. Second line contains T the number of queries. Next T lines contains two space separated integers L and R.

OUTPUT:
For each query print length of correct parentheses subsequence in new line.

Constraints
1<=|Length of the string|<=10^5
1<=T<=10^5
1<=L<=R<=10^5