Tautology_SOLVED

/*

CODECHEF

PROBLEM CODE : TAUT

*/

#include <stdio.h>

#include <string.h>
#define S(a,b,c) (b=(a)?(c):(b))
 
int f[30];
char z[3][130];
 
int A(int q, int w)
{
if(q>=w)
return B()+(f[28]=0);
if(!(f[z[1][q]-'a']=0)&&!A(q+1,w))
return 0;
return !!A(q+(f[z[1][q]-'a']=1),w);
}
 
int B()
{
int t1, t2;
char *p=&z[0][f[28]];
if(*p>='a'&&*p<='z')
return f[z[0][f[28]++]-'a'];
if(*p=='N')
{
f[28]++;
t1=B();
return t1^1;
}
else if(*p=='C'||*p=='D'||*p=='I'||*p=='E')
{
f[28]++;
t1=B();
t2=B();
return (*p=='C')?(t1&t2):((*p=='D')?(t1|t2):((*p=='I')?((t1^1)|t2):((t1&t2)|((t1^1)&(t2^1)))));
}
return 0;
}
 
int main()
{
int fall, i, s;
for(scanf("%d",&fall); fall--;)
{
for(i=-!(s=!scanf("%s",z[0])),f[27]=strlen(z[0]); z[0][++i]!='\0'; S(z[0][i]>='a'&&z[0][i]<='z'&&!z[2][z[0][i]-'a'],z[2][z[0][i]-'a'],1+(z[1][s++]=z[0][i])-z[0][i]));
printf(A(0,s)?"YES\n":"NO\n");
for(i=-1; ++i<26; f[i]=z[2][i]=0);
}
return 0;
}