#include <iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

char a[10002];

int b[10002];

int n,ans;

int dp(int x)

{

int i,j,max;

b[0]=1;

for(i=1;i<=x;i++)

{max=1;

for(j=0;j<i;j++)

if(a[j]<a[i] && max<b[j]+1) max=b[j]+1;

b[i]=max;

}

}

int main( )

{

int i,j,len;

cin>>n;

for(i=1;i<=n;i++)

{

scanf("%s",a);

len=strlen(a) ;

dp(len-1);

ans=1;

for(j=0;j<len;j++)

if(ans<b[j]) ans=b[j];

cout<<ans<<endl ;

}

}

 

******************************************************************88

#include <iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

char a[10002];

int b[10002];

int n,ans;

int dp(int x)

{

int i,j,max;

ans=b[0]=1;

for(i=1;i<=x;i++)

{max=1;

for(j=0;j<i;j++)

if(a[j]<a[i] && max<b[j]+1) max=b[j]+1;

b[i]=max;

if(b[i]>ans) ans=b[i];

}

}

int main( )

{

int i,j,len;

cin>>n;

for(i=1;i<=n;i++)

{

scanf("%s",a);

len=strlen(a) ;

dp(len-1);

cout<<ans<<endl ;

}

}