#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int maxsize=100;
static char arr[100];
int top=-1;
char queue[100];
int front=-1;
int rear=-1;
char enqueue(char data){
if(rear+1>=100){
return 0;}
else{
queue[rear+1]=data;
rear++;
return 1;
}}
char dequeue(){
if(front==rear){
return 0;}
else{
char data=queue[front+1];
front++;
return(data);
}}
 
void push(char new){
if(top==maxsize-1){
printf("full stack\n");
}
else{
top++;
arr[top]=new;
}}
char pop(){
 
char tmp;
if(top==-1){
printf("empty");
return tmp;
}
else{
top--;
return (arr[top+1]);
}}
int main(){
int t=1;
int f=0;
 
char stack[10];
char queue[10];
 
char aa[100];
int stringsize=strlen(aa);
 
int i=0;
int counter=0;
scanf("%d\n",&counter);
for(int k=0;k<=counter;k++){
scanf("%c\n",aa);
while(i<stringsize){
 
 
push(aa[i]);
enqueue(aa[i]);
i++;}
int n=0;
while(n<stringsize){
 stack[n]=pop();
queue[n]=dequeue();
if(stack[n]==queue[n]){
 
n++;}
else
{
printf("%d\n",f);
 
}
}
if(stack==queue){
printf("%d\n",t);
}
}
 return 0;
 
}