// tested by Hightail: https://github.com/dj3500/hightail #include <iostream> #include <cstdio> #include <string> #include <vector> #include <set> #include <map> #include <queue> #include <cmath> #include <algorithm> #include <sstream> #include <stack> #include <cstring> #include <iomanip> #include <ctime> #include <cassert> using namespace std; #define pb push_back #define INF 1001001001 #define FOR(i,n) for(int (i)=0;(i)<(n);++(i)) #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i)) #define mp make_pair #define pii pair<int,int> #define ll long long #define vi vector<int> #define SZ(x) ((int)((x).size())) #define fi first #define se second #define wez(n) int (n); scanf("%d",&(n)); #define wez2(n,m) int (n),(m); scanf("%d %d",&(n),&(m)); #define wez3(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k)); inline void pisz(int n) { printf("%d\n",n); } template<typename T,typename TT> ostream& operator<<(ostream &ss,pair<T,TT> t) {return ss<<"("<<t.first<<","<<t.second<<")";} template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR(i,SZ(t))s<<t[i]<<" ";return s; } #define DBG(vari) cout<<"["<<__LINE__<<"] "<<#vari<<" = "<<(vari)<<endl; #define ALL(t) t.begin(),t.end() #define FOREACH(i,t) for (__typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define TESTS wez(testow)while(testow--) #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define REMAX(a,b) (a)=max((a),(b)); #define REMIN(a,b) (a)=min((a),(b)); #define IOS ios_base::sync_with_stdio(0); string s; struct Regex { Regex *le, *ri; int ty; #define STAR 1 #define CONC 2 #define ALTER 3 #define LETTER 4 char letter; void build (int a, int b) { //DBG(mp(a,b)); REP(x,0,500) can[x] = 0; le = 0; ri = 0; assert(a <= b); if (a == b) { assert(islower(s[a])); ty = LETTER; letter = s[a]; } else { // is there an upperlevel alternation? int open = 0; int found = -1; REP(x,a,b) { if (s[x] == '(') ++open; if (s[x] == ')') --open; if (s[x] == '|') { if (open == 0) { found = x; break; } } } if (found != -1) { le = new Regex; le->build(a, found - 1); ri = new Regex; ri->build(found + 1, b); ty = ALTER; } else { // (...)* // a* // concat // (...) // (...)*(...)* // (...)*** // (...)*(...)*** // co jest na poczatku? // (, a if (islower(s[a])) { int x = a; while (x+1 <= b && s[x+1] == '*') ++x; // s[x] nie jest *, lub x == b if (x == b) { // a******* ty = STAR; le = new Regex; le->build(a,a); } else { ty = CONC; le = new Regex; le->build(a, x); ri = new Regex; ri->build(x+1, b); } } else if (s[a] == '(') { int open = 1; int found = -1; REP(x,a+1,b) { if (s[x] == '(') ++open; if (s[x] == ')') --open; if (open == 0) { found = x; break; } } assert(found != -1); int x = found; if (x == b) { //DBG("tu"); // (.....) build(a + 1, b - 1); } else { while (x+1 <= b && s[x+1] == '*') ++x; if (x == b && s[b] == '*') { // (...)* ty = STAR; le = new Regex; le->build(a, b-1); } else { ty = CONC; le = new Regex; le->build(a, x); ri = new Regex; ri->build(x+1,b); } } } else { assert(0); } } } //DBG("done")DBG(mp(a,b)); } bool can[505]; void compute () { if (le) le->compute(); if (ri) ri->compute(); if (ty == STAR) { can[0] = 1; REP(x,1,500) if (le->can[x]) { for (int y = x; y <= 500; y += x) can[y] = 1; } } else if (ty == CONC) { REP(x,0,500) if (le->can[x]) REP(y,0,500) if (x+y <= 500) if (ri->can[y]) can[x+y] = 1; } else if (ty == ALTER) { REP(x,0,500) can[x] = le->can[x] || ri->can[x]; } else { // LETTER can[1] = 1; } } }; int main () { TESTS { wez(len) cin >> s; //DBG(s) Regex ex; //ex.build(3,3); //return 0; ex.build(0, SZ(s)-1); //DBG(len) //return 0; ex.compute(); int res = -1; REP(x,len,500) if (ex.can[x]) { res = x; break; } pisz(res); } }