#只60%過，找不出問題
#一回合可拿取的所有情況
takeList = [1<<11,#A
1<<10,#B
1<<9,#C
1<<8,#D
1<<7,#E
1<<6,#F
1<<5,#G
1<<4,#H
1<<3,#I
1<<2,#J
1<<1,#K
1<<0,#L
1<<11|1<<8,#AD
1<<9|1<<8,#CD
1<<8|1<<7,#DE
1<<8|1<<4,#DH
1<<10|1<<7,#BE
1<<7|1<<6,#EF
1<<7|1<<3,#EI
1<<5|1<<4,#GH
1<<4|1<<3,#HI
1<<4|1<<1,#HK
1<<3|1<<2,#IJ
1<<3|1<<0 #IL
]
# 所有情況的list
answer=[-1 for i in range(4096)]
# 先手必敗的初始設定=0
for i in takeList:
answer[i]=0
#動態規劃完成answer[]
for i in range(1,len(answer)):
if(answer[i]==-1):
result = 0
for j in range(len(takeList)):
#拿完剩下的棋子，回頭找動態規劃後儲存的值，只要一個為零，那就代表這個拿法一定贏
reverse = 4095-takeList[j]
index = reverse & i
if(answer[index]==0):
result=1
break
answer[i]=result
n = int(input())
results=''
for i in range(n):
s= input()
num=0
for j in range(len(s)):
num +=int(s[j])<<(11-int(j))
results +=str(answer[num])
print(results)