#include <cmath>
#include <string.h>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define MAX_POINTER 50000
using namespace std;
typedef struct node {
	int num;
    vector<struct node*> zedges;
    vector<struct node*> oedges;
    int mark[501];
} Node;
char s[505];
Node* save[MAX_POINTER];
int co,co_num;
void parse(int h1,int h2,Node* start,Node* stop) {
	//printf("%d %d %d\n",h1,h2,co_num);
    //find '|'
    int num_paren = 0;
    int first = h1;
    bool mark = 0;
    for(int i=h1;i<=h2;i++) {
        if(s[i]=='(') num_paren++;
        else if(s[i]==')') num_paren--;
        else if(s[i]=='|' && num_paren==0) {
            Node* t_start=(Node*)calloc(1,sizeof(Node));
			save[co_num]= t_start;
			t_start->num=co_num++;
            Node* t_stop=(Node*)calloc(1,sizeof(Node));
			save[co_num]= t_stop;
			t_stop->num=co_num++;
            parse(first,i-1,t_start,t_stop);
            start->zedges.push_back(t_start);
            t_stop->zedges.push_back(stop);
            first=i+1;
            mark=1;
        }
    }
    if(mark) {
        Node* t_start=(Node*)calloc(1,sizeof(Node));
			save[co_num]= t_start;
			t_start->num=co_num++;
        Node* t_stop=(Node*)calloc(1,sizeof(Node));
			save[co_num]= t_stop;
			t_stop->num=co_num++;
        parse(first,h2,t_start,t_stop);
        start->zedges.push_back(t_start);
        t_stop->zedges.push_back(stop);
        first=h2+1;
        mark=1;
        return;
    }
    //else
    int open=-1;
    Node* rev = start;
    Node* pre_rev;
	num_paren=0;
    for(int i=h1;i<=h2;i++) {
        if(s[i]=='(') {
            if(num_paren==0) {
                open=i;
            }
            num_paren++;
        }
        else if(s[i]==')') {
            num_paren--;
            if(num_paren==0) {
                Node* t_start=(Node*)calloc(1,sizeof(Node));
				save[co_num]= t_start;
				t_start->num=co_num++;
                Node* t_stop=(Node*)calloc(1,sizeof(Node));
				save[co_num]= t_stop;
				t_stop->num=co_num++;
                parse(open+1,i-1,t_start,t_stop);
                start->zedges.push_back(t_start);
                start = t_stop;
				pre_rev = rev;
                rev = t_stop;
            }
        }
        else if(num_paren==0 && s[i]=='*') {
			pre_rev->zedges.push_back(start);
            start->zedges.push_back(pre_rev);
        }
        else if(num_paren==0){
			//printf("%d %d %d %d\n",h1,h2,i,co_num);
            Node *t_start = (Node*) calloc(1,sizeof(Node));
			save[co_num]= t_start;
			t_start->num=co_num++;
            start->oedges.push_back(t_start);
            start= t_start;
			pre_rev = rev;
            rev = t_start;
        }
    }
	start->zedges.push_back(stop);
}

void dfs(Node* cur,int h) {
	if(h>500) return;
	if(cur->mark[h]==co) return;
	cur->mark[h]=co;
	for(int i=0;i<cur->zedges.size();i++) {
		dfs(cur->zedges[i],h);
	}
	for(int i=0;i<cur->oedges.size();i++) {
		dfs(cur->oedges[i],h+1);
	}
}


int main() {
    int t,len;
    scanf("%d",&t);
    for(int r=0;r<t;r++) {
        scanf("%d",&len);
        scanf("%s",s);
        Node* start=(Node*)calloc(1,sizeof(Node));
			save[co_num]= start;
			start->num=co_num++;
        Node* stop=(Node*)calloc(1,sizeof(Node));
			save[co_num]= stop;
			stop->num=co_num++;
        int n = strlen(s);
        parse(0,n-1,start,stop);
		/*for(int i=0;i<co_num;i++) {
			printf("%d\n",i);
			printf("  0 : ");
			for(int j=0;j<save[i]->zedges.size();j++) {
				printf("%d ",save[i]->zedges[j]->num);
			}
			printf("\n");
			printf("  1 : ");
			for(int j=0;j<save[i]->oedges.size();j++) {
				printf("%d ",save[i]->oedges[j]->num);
			}
			printf("\n");
		}*/
        co++;
		dfs(start,0);
		int ans=-1;
		for(int i=len;i<=500;i++) {
			if(stop->mark[i]==co) {
				ans=i;
				break;
			}
		}
		printf("%d\n",ans);
		for(int i=0;i<co_num;i++) {
			save[i]->zedges.clear();
			save[i]->oedges.clear();
			free(save[i]);
		}
		co_num=0;
    }
    return 0;
}