Poetry is a form of literature that uses aesthetic and rhythmic qualities of language. There are many famous poets in the contemporary era. It is said that a few ACM-ICPC contestants can even write poetic code. Some poems has a strict rhyme scheme like "ABABA" or "ABABCAB". For example, "niconiconi" is composed of a rhyme scheme "ABABA" with A = "ni" and B = "co".

More technically, we call a poem pretty if it can be decomposed into one of the following rhyme scheme: "ABABA" or "ABABCAB". The symbolA, B and C are different continuous non-empty substrings of the poem. By the way, punctuation characters should be ignored when considering the rhyme scheme.

You are given a line of poem, please determine whether it is pretty or not.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is a line of poem S (1 <= length(S) <= 50). S will only contains alphabet characters or punctuation characters.

Output

For each test case, output "Yes" if the poem is pretty, or "No" if not.

Sample Input

3
niconiconi~
pettan,pettan,tsurupettan
wafuwafu

Sample Output

Yes
Yes
No

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 55

char a[N],b[N];
int k;
int vis[N];

int judge()
{
    int i,j;

    char x[N],y[N],z[N];
    int xx,yy,zz;

    for(i=2;i*2<k;i++)
    {
         for(j=0;j<i;j++)
            {
                x[j]=b[j];
            }
          x[j]='\0';

          yy=0;
          for(j;j<i*2;j++)
          {
              y[yy++]=b[j];
          }
          y[yy]='\0';

          if(strcmp(x,y)!=0)  continue;

          zz=0;
          for(j;b[j];j++)
            z[zz++]=b[j];
          z[zz]='\0';

          if(zz>=i) continue;

          char A[N],B[N];
          int AA,BB;

          for(j=0;j<zz;j++)
            A[j]=b[j];

          A[j]='\0';

          if(strcmp(A,z)!=0) continue;

          BB=0;
          for(j;j<i;j++)
            B[BB++]=b[j];
          B[BB]='\0';

          if(strcmp(A,B)==0)  continue;

          //printf("x=%s\ny=%s\nz=%s\n",x,y,z);
          //printf("A=%s\nB=%s\n",A,B);
          return 1;
    }
    return 0;
}

int judgee()
{
    int i,j;
    int vis[N];
    char x[N],y[N],z[N],w[N];
    int xx,yy,zz,ww;

    for(i=2;i*3<k;i++)
    {
        memset(vis,0,sizeof(vis));

        int xx=0;
        for(j=0;j<i;j++)
        {
            x[j]=b[j];
            vis[j]=1;
        }
        x[j]='\0';

        yy=0;
        for(j;j<i*2;j++)
        {
            y[yy++]=b[j];
            vis[j]=1;
        }
        y[yy]='\0';

        zz=0;
        j=k-i;

        for(;b[j];zz++,j++)
        {
            vis[j]=1;
            z[zz]=b[j];
        }
        z[zz]='\0';

        ww=0;
        for(j=i*2;!vis[j];j++)
        {
            w[ww++]=b[j];
        }
        w[ww]='\0';

        if(strcmp(x,y)!=0) continue;

        if(strcmp(y,z)!=0) continue;

        char A[N],B[N];
        int AA,BB;

        for(j=1;j<i;j++)
        {
            int jj;
            for(jj=0;jj<j;jj++)
                A[jj]=b[jj];
              A[jj]='\0';

            BB=0;
            for(jj;jj<i;jj++)
                B[BB++]=b[jj];
            B[BB]='\0';

            if(strcmp(B,A)==0) continue;

            if(strcmp(B,w)==0)  continue;

            if(strcmp(A,w)==0)  continue;

             //printf("x=%s\ny=%s\nw=%s\nz=%s\n",x,y,w,z);
             //printf("A=%s\nB=%s\n",A,B);

            return 1;
        }
    }

    return 0;
}
int main()
{
   int i,t;
   scanf("%d",&t);
   while(t--)
   {
       scanf("%s",a);
       int len=strlen(a);
       k=0;
       for(i=0;i<len;i++)
        if(a[i]>='a'&&a[i]<='z'||a[i]>='A'&&a[i]<='Z')
        b[k++]=a[i];
       b[k]='\0';

       if(judge())
       {
           printf("Yes\n");
           continue;
       }

       if(judgee())
       {
           printf("Yes\n");
           continue;
       }

       printf("No\n");
   }
   return 0;
}

/*

2
ababa


ababcab

*/