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