#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");
	}
}