B'A sequence of round and square brackets is given. You can change the sequence by performing the following operations: 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 <= l < r <= n . For every substring s[l ... r] , find the minimum cost to pay to make it a correct bracket sequence. It is guaranteed that the substring s[l ... 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 ... r] is given from the initially given string s . A correct bracket sequence is a sequence that can be built according the following rules: E.g. the sequences "", "(()[])", "[()()]()" and "(())()" are correct bracket sequences whereas "(", "[(])" and ")))" are not. The first line contains one integer t ( 1 <= t <= 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 <= q <= 2 cdot 10^5 ) -- the number of queries. Then q lines follow, each of them contains two integers l and r ( 1 <= l < r <= n where n is the length of s ). It is guaranteed that the substring s[l ... 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 . For each test case output in a separate line for each query one integer x ( x ge 0 ) -- the minimum cost t'...