A sequence of round and square brackets is given. You can change the sequence by performing the following operations:

change the direction of a bracket from opening to closing and vice versa without changing the form of the bracket: i.e. you can change '(' to ')' and ')' to '('; you can change '[' to ']' and ']' to '['. The operation costs $0$ burles.

change any square bracket to round bracket having the same direction: i.e. you can change '[' to '(' but not from '(' to '['; similarly, you can change ']' to ')' but not from ')' to ']'. The operation costs $1$ burle.

The operations can be performed in any order any number of times.

You are given a string $s$ of the length $n$ and $q$ queries of the type "l r" where $1 \le l < r \le n$. For every substring $s[l \dots r]$, find the minimum cost to pay to make it a correct bracket sequence. It is guaranteed that the substring $s[l \dots r]$ has an even length.

The queries must be processed independently, i.e. the changes made in the string for the answer to a question $i$ don't affect the queries $j$ ($j > i$). In other words, for every query, the substring $s[l \dots r]$ is given from the initially given string $s$.

A correct bracket sequence is a sequence that can be built according the following rules:

an empty sequence is a correct bracket sequence;

if "s" is a correct bracket sequence, the sequences "(s)" and "[s]" are correct bracket sequences.

if "s" and "t" are correct bracket sequences, the sequence "st" (the concatenation of the sequences) is a correct bracket sequence.

E.g. the sequences "", "(()[])", "[()()]()" and "(())()" are correct bracket sequences whereas "(", "[(])" and ")))" are not.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

For each test case, the first line contains a non-empty string $s$ containing only round ('(', ')') and square ('[', ']') brackets. The length of the string doesn't exceed $10^6$. The string contains at least $2$ characters.

The second line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, each of them contains two integers $l$ and $r$ ($1 \le l < r \le n$ where $n$ is the length of $s$). It is guaranteed that the substring $s[l \dots r]$ has even length.

It is guaranteed that the sum of the lengths of all strings given in all test cases doesn't exceed $10^6$. The sum of all $q$ given in all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case output in a separate line for each query one integer $x$ ($x \ge 0$) — the minimum cost to pay to make the given substring a correct bracket sequence.


-----Examples-----

Input
3
([))[)()][]]
3
1 12
4 9
3 6
))))))
2
2 3
1 4
[]
1
1 2
Output
0
2
1
0
0
0


-----Note-----

Consider the first test case. The first query describes the whole given string, the string can be turned into the following correct bracket sequence: "([()])()[[]]". The forms of the brackets aren't changed so the cost of changing is $0$.

The second query describes the substring ")[)()]". It may be turned into "(()())", the cost is equal to $2$.

The third query describes the substring "))[)". It may be turned into "()()", the cost is equal to $1$.

The substrings of the second test case contain only round brackets. It's possible to prove that any sequence of round brackets having an even length may be turned into a correct bracket sequence for the cost of $0$ burles.

In the third test case, the single query describes the string "[]" that is already a correct bracket sequence.

Difficulty: HARD
Tags: Greedy algorithms

Dynamic programming

Data structures

Constructive algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input().strip()
	n = len(s)
	odd = [0]
	even = [0]
	for i in range(n):
		if s[i] == '[' or s[i] == ']':
			if i % 2 == 0:
				even.append(even[-1] + 1)
				odd.append(odd[-1])
			else:
				odd.append(odd[-1] + 1)
				even.append(even[-1])
		else:
			even.append(even[-1])
			odd.append(odd[-1])
	for query in range(int(input())):
		(l, r) = [int(x) for x in input().split(' ')]
		oddS = odd[r] - odd[l - 1]
		evenS = even[r] - even[l - 1]
		print(abs(oddS - evenS))


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	X = input().strip()
	n = len(X)
	R = [0]
	L = [0]
	for i in range(n):
		if i % 2 == 0:
			if X[i] == '[' or X[i] == ']':
				R.append(R[-1] + 1)
			else:
				R.append(R[-1])
			L.append(L[-1])
		else:
			if X[i] == '[' or X[i] == ']':
				L.append(L[-1] + 1)
			else:
				L.append(L[-1])
			R.append(R[-1])
	q = int(input())
	for queries in range(q):
		(l, r) = map(int, input().split())
		RS = R[r] - R[l - 1]
		LS = L[r] - L[l - 1]
		print(abs(RS - LS))