#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; double PI = acos(-1); double EPS = 1e-7; int INF = 1000000000; LL INFLL = 1000000000000000000LL; #define fi first #define se second #define mp make_pair #define pb push_back #define input(in) freopen(in,"r",stdin) #define output(out) freopen(out,"w",stdout) #define MIN(a, b) (a) = min((a), (b)) #define MAX(a, b) (a) = max((a), (b)) #define RESET(a, b) memset(a,b,sizeof(a)) #define ALL(a) (a).begin(), (a).end() #define SIZE(a) (int)a.size() #define SORT(a) sort(ALL(a)) #define UNIQUE(a) (a).erase( unique( ALL(a) ), (a).end() ) #define FOR(a, b, c) for (int (a)=(b); (a)<=(c); (a)++) #define FORD(a, b, c) for (int (a)=(b); (a)>=(c); (a)--) #define FORIT(a, b) for (__typeof((b).begin()) a=(b).begin(); a!=(b).end(); a++) int mx[8] = {-1,1,0,0,-1,-1,1,1}; int my[8] = {0,0,-1,1,-1,1,-1,1}; // ----- // char s[105]; int lim = 100; int dp[105][105][505]; int vs[105][105][505]; int T; int go(int l,int r,int target) { //cout << l << " " << r << " " << target << endl; if (l > r) return (target == 0); if (target < 0) return 0; if (vs[l][r][target] == T) { return dp[l][r][target]; } vs[l][r][target] = T; int balance = 0; bool fail = 0; FOR(a,l,r-1) { if (s[a] == '(') balance++; if (s[a] == ')') balance--; if (balance == 0) { fail = 1; break; } } if (!fail && s[r] == ')' && balance == 1) return dp[l][r][target]=go(l+1,r-1,target); balance = 0; int nx = -1; FOR(a,l,r) { if (s[a] == '(') balance++; if (s[a] == ')') { balance--; if (balance == 0 && nx == -1) nx = a; } if (s[a] == '|' && balance == 0) { //cout << "found " << l << " " << r << " " << target << endl; if (go(l,a-1,target) || go(a+1,r,target)) { return dp[l][r][target]=1; } return dp[l][r][target]=0; } } if ('a' <= s[l] && s[l] <= 'z') { if (l == r || s[l+1] != '*') { return dp[l][r][target]=go(l+1,r,target-1); } else { FOR(a,0,500) { if (go(l+2,r,target-a)) { return dp[l][r][target]=1; } } } } else { if (nx == r || s[nx+1] != '*') { FOR(a,0,500) { if (go(l,nx,a) && go(nx+1,r,target-a)) { return dp[l][r][target]=1; } } } else { FOR(a,0,500) { if (go(l,nx,a)) { for(int b=0;b<=500;b+=a) { if (go(nx+2,r,target-b)) return dp[l][r][target]=1; if (a == 0) break; } } } } } return dp[l][r][target]=0; } int main() { int tc; scanf("%d",&tc); FOR(_T,1,tc) { T = _T; int n; scanf("%d",&n); scanf("%s",s); bool ada = 0; FOR(a,n,500) { if (go(0,strlen(s)-1,a)) { printf("%d\n",a); ada = 1; break; } } if (!ada) printf("-1\n"); } }