1
#include <bits/stdc++.h>
2
using namespace std;
3
#define LL long long
4
#define INF 0x3f3f3f3f
5
const int N = 2e6+5;
6
struct Node {
7
	int ls,rs;
8
} no[N];
9
int ind, cnt;
10
string s;
11
int sum[N]; // sum[i] 表示 以 i 点为根的子树的装饰物总数
12
 
13
// 建树 
14
void build(int &u) {
15
	u = ++cnt;
16
	ind++;
17
	if(s[ind]==')')			// 空结点 
18
		sum[u] = 0;
19
	else if(s[ind]=='B')	// 装饰物 
20
		sum[u] = 1, ind++;		// 跳过 B 字符 
21
	else {					// 左括号，有左右子树 
22
		build(no[u].ls), build(no[u].rs);	
23
		sum[u] = sum[no[u].ls] + sum[no[u].rs];
24
	}
25
	ind++;	// 取走 右括号 
26
}
27
 
28
void solve() {
29
	int t;
30
	cin >> t;
31
	for(int _=0; _<t; _++) {
32
		cin >> s;
33
		int root;
34
		cnt = 0, ind = 0;
35
		memset(no,0,sizeof(no));
36
		build(root);
37
		int  op = dfs(root,sum[root]);
38
		if(op==INF) cout << "impossible\n";
39
		else cout << op << "\n";
40
	}
41
}