#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>

#define pb push_back
#define mp make_pair
#define ll long long
#define FOR(i, A, N) for(int (i) = (A); (i) < (N); (i)++)
#define REP(i, N) for(int (i) = 0; (i) < (N); (i)++)

using namespace std;
int T;
int L, rl;
char rex[111];
int br[111];
int dp[111][555];

int solve(int pos, int clen) {
//	printf("%d %d\n", pos, clen);
	int& ans = dp[pos][clen];
	if(clen > 500)
		return clen;
	if(pos == rl) {
		if(clen >= L)
			return clen;
		else
			return 504;
	}
	if(ans == -1) {
		ans = 504;
		if(rex[pos] == '*') {
			ans = solve(pos+1, clen);
			if(rex[pos-1] == ')')
				ans = min(ans, solve(br[pos-1], clen));
			else
				ans = min(ans, solve(pos-1, clen));
		} else if(rex[pos] == ')') {
			ans = solve(pos+1, clen);
		} else if(rex[pos] == '|') {
			int b = 0;
			while(pos < rl && (rex[pos] != ')' || b != 0)) {
				if(rex[pos] == ')') b--;
				else if(rex[pos] == '(') b++;
				pos++; 
			}
			ans = solve(pos, clen);
		} else if(rex[pos] == '(') {
			int b = 0;
			ans = solve(pos+1, clen);
			for(int i = pos+1; i < br[pos]; i++) {
				if(rex[i] == '(') b++;
				else if(rex[i] == ')') b--;
				if(rex[i] == '|' && b == 0) {
					ans = min(ans, solve(i+1, clen));
				}
			}
			int bound = br[pos];
			if(bound+1 < rl && rex[bound+1] == '*') {
				ans = min(ans, solve(bound+1, clen));
			}
		} else {
			ans = min(ans, solve(pos+1, clen+1));
			if(rex[pos+1] == '*')
				ans = min(ans, solve(pos+2, clen));
		}
	}
	return ans;
}


int main() {
	scanf("%d", &T);
	REP(t, T) {
		memset(dp, -1, sizeof(dp));
		scanf("%d", &L);
		scanf("%s", rex+1);
		rex[0] = '(';
		rl = strlen(rex);
		rex[rl++] = ')';
		rex[rl] = '\0';
		stack<int> sbr;
		REP(i, rl) {
			if(rex[i] == '(')
				sbr.push(i);
			else if(rex[i] == ')') {
				int x = sbr.top();
				sbr.pop();
				br[x] = i;
				br[i] = x;
			}
		}
		printf("%d\n", solve(0, 0) > 500 ? -1 : solve(0, 0));
	}
	return 0;
}