4286

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF int(1e9+1)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX (1<<19)
typedef map<ll,int> mp;
char s[1<<24];
int L,W[MX],D,S[MX],X;
vi g[MX];
int rc(int&u){
    int I=u++;
    if(s[L]^91){
        sscanf(s+L,"%d",W+I);
        while(isdigit(s[L]))++L;
        return S[I]=1;
    }
    ++L,g[I].PB(u),S[I]+=rc(u),++L,g[I].PB(u),S[I]+=rc(u),++L;
    return S[I];
}
void ud(mp&G,ll I,int p){int a=G.count(I)?min(p,G[I]):p;G[I]=a;}
mp dfs(int u){
    mp G,a,b;
    if(g[u].empty()){
        G[W[u]]=0;
        return G;
    }
    assert(g[u].size()==2u);
    a=dfs(g[u][0]),b=dfs(g[u][1]);
    int X=S[g[u][0]],Y=S[g[u][1]];
    for(auto&h:a)if(b.count(h.aa))ud(G,h.aa*2,h.bb+b[h.aa]);
                 else ud(G,h.aa*2,h.bb+Y);
    for(auto&h:b)if(!a.count(h.aa))ud(G,h.aa*2,h.bb+X);
    return G;
}
int main(void){
    IN(_)F(_){
        for(auto&h:g)h.clear();
        scanf("%s",s),CL(S,D=L=0),rc(D),X=INF;
        mp G=dfs(0);
        for(auto&h:G)X=min(X,h.bb);
        printf("%d\n",X);
    }
    return 0;
}