#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <set>

#include <string>

#include <algorithm>

#include <vector>

#include <iostream>

#include <queue>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define maxn 1000005

#define inf (0x3f3f3f3f)

int read()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

int m;

int a[101],S,T;

bool cmp(int a,int b)

{return a>b;}

int h[300001],to[300001],ne[300001],fl[300001],en=0;

int map[300001];

void add (int a,int b,int r)

{

	to[en]=b;

	fl[en]=r;

	ne[en]=h[a];

	h[a]=en++;

	to[en]=a;

	fl[en]=0;

	ne[en]=h[b];

	h[b]=en++;

}

int mp[300001];

bool tell()

{

    memset(mp,-1,sizeof mp);

    queue <int> q;

    while (!q.empty()) q.pop();

    q.push(S); mp[S]=0;

    while (!q.empty())

    {

        int x=q.front(); q.pop();

        for (int i=h[x];i>=0;i=ne[i])

        {

            if (fl[i]>0&&mp[to[i]]==-1)

            {

                mp[to[i]]=mp[x]+1;

                q.push(to[i]);

            }

        }

    }

    if (mp[T]==-1) return false;

    return true;

}

int zeng(int k,int now)

{

    if (k==T) return now;

    int ret=0;

    for (int i=h[k];i>=0&&ret<now;i=ne[i])

    {

        if (fl[i]>0&&mp[to[i]]==mp[k]+1)

        {

            int tmp=zeng(to[i],min(now-ret,fl[i]));

            fl[i]-=tmp; fl[i^1]+=tmp; ret+=tmp;

        }

    }

    if (ret==0) mp[k]=-1;

    return ret;

}

int dinic()

{

    int r=0,t;

    while (tell()) while (t=zeng(S,inf)) r+=t;

    return r;

}

int hash[101][101],sum=0;

bool test(int mid)

{

	int cnt=a[0]; S=0;

	for (int i=1;i<=a[0];++i)

		for (int j=1;j<=a[0];++j)

			hash[i][j]=++cnt;

	T=++cnt;

	for (int i=1;i<=a[0];++i) add(S,i,a[i]);

	for (int i=1;i<=a[0];++i)

		for (int j=1;j<i;++j)

		if (j!=i){

			add(hash[i][j],T,1);

			if (a[i]<a[j]&&i<=mid) add(i,hash[i][j],1);

			else

			{

				add(i,hash[i][j],1);

				add(j,hash[i][j],1);

			}

		}

	int out=dinic();

	if (out>=sum) return true;

	else return false;

}

void init()

{

	memset(h,-1,sizeof h);

	en=0;

}

void solve()

{

	int l=1,r=a[0];

	while (l<r)

	{

		init();

		int mid=(l+r)/2+1;

		if (test(mid)) l=mid;

		else r=mid-1;

	}

	printf("%d\n",l);

}

char s[1000];

int main()

{

	cin>>m; gets(s);

	while (m--)

	{

		sum=0;

		cin.getline(s,100);

		int x=0; a[0]=0;

		for (int i=0;i<strlen(s);++i)

		{

			if (s[i]>='0'&&s[i]<='9')

				a[++a[0]]=s[i]-'0',sum+=a[a[0]];

		}

		a[++a[0]]=x; sum+=x;x=0;a[0]--;

		sort(a+1,a+a[0]+1,cmp);

		solve();

	}

}