#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

const int INF = 1<<29;
typedef long long ll;

inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

const int OR = 1, STAR = 2, SINGLE = 3, CONCAT = 4;
int N, len, match[147];
char in[147];

int node_cnt;
struct Node
{
	Node() {
		index = node_cnt++;
		left = right = NULL;
	}
	int type, index;
	Node * left, * right;
};

Node * parse(int be, int en)
{
	// outer parentheses
	if (in[be] == '(' && in[en] == ')' && match[be] == en)
		return parse(be+1, en-1);

	// single char
	if (be == en)
	{
		Node * node = new Node();
		node->type = SINGLE;
		return node;
	}

	// solve or
	int paren = 0;
	for (int i = be; i <= en; ++i)
		if (in[i] == '(') ++paren;
		else if (in[i] == ')') --paren;
		else if (in[i] == '|' && !paren) 
		{
			Node * node = new Node();
			node->type = OR;
			node->left = parse(be, i-1);
			node->right = parse(i+1, en);
			return node;
		}
	
	Node * right;
	if (in[en] == '*')
	{
		right = new Node();
		right->type =  STAR;
		if (in[en-1] == ')')
		{
			right->left = parse(match[en-1], en-1);
			en = match[en-1]-1;
		}
		else
		{
			right->left = parse(en-1, en-1);
			en = en-2;
		}
	}
	else if (in[en] == ')')
	{
		right = parse(match[en], en);
		en = match[en]-1;
	}
	else
	{
		right = parse(en, en);
		en = en-1;
	}
	if (en < be) return right;

	Node * node = new Node();
	node->type = CONCAT;
	node->left = parse(be, en);
	node->right = right;
	return node;
}

int dp[200][501];
int go(Node * node, int len)
{
	int & res = dp[node->index][len];
	if (res != -1) return res;
	res = 0;
	if (node->type == SINGLE)
	{
		if (len == 1) res = 1;
	}
	else if (node->type == CONCAT)
	{
		for (int i = 0; i <= len && !res; ++i)
			res = go(node->left, i) && go(node->right, len-i);
	}
	else if (node->type == STAR)
	{
		if (!len) res = 1;
		for (int i = 1; i <= len && !res; ++i)
			if (len % i == 0)
				res = go(node->left, len / i);
	}
	else if (node->type == OR)
		res = go(node->left, len) || go(node->right, len);

	return res;
}

int main()
{
	int T;
	scanf("%d", &T);

	while (T--)
	{
		scanf("%d\n", &N);
		gets(in);
		len = strlen(in);
		stack<int> st;
		REP(i, len)
			if (in[i] == '(') st.push(i);
			else if (in[i] == ')')
			{
				int n = st.top();
				st.pop();
				match[n] = i;
				match[i] = n;
			}

		node_cnt = 0;
		Node * root = parse(0, len-1);
		memset(dp, -1, sizeof(dp));
		bool ok = false;
		FOR(i, N, 500)
			if (go(root, i))
			{
				printf("%d\n", i);
				ok = true;
				break;
			}
		if (!ok) printf("-1\n");
	}

	return 0;
}