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