// 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);
   }
}