There are $5$ cities in the country.
The map of the country is given below.
The tour starts from the red city.

Each road is associated with a character.
Initially, there is an empty string.
Every time a road has been travelled the character associated gets appended to the string.
At the green city either the string can be printed or the tour can be continued.
In the problem, you are given a string tell whether it is possible to print the string while following the rules of the country?

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains a single line of input, a string $ s  $. The string consists only of $0's$ and $1's$.

-----Output:-----
For each testcase, output "YES" or "NO" depending on the input.

-----Constraints-----
- 
$1 \leq T \leq 10000$
- 
$1 \leq length of each string \leq 10000$
- 
$ 1 \leq Summation length \leq 10^5$

-----Sample Input:-----
1
100

-----Sample Output:-----
NO

-----EXPLANATION:-----

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 s=input()
 if len(s)<4:
  print("NO")
 else:
  if s[-4:]=="1000":
   print("YES")
  else:
   print("NO")

# cook your dish here
t = int(input())
for i in range(t):
 n = input()
 if len(n)>=4:
  if n . endswith ('1000'):
   print("YES")
  else:
   print("NO")
 else:
  print("NO")

t = int(input())
for _ in range(t):
 s = input()
 if s.endswith('1000'):
  print('YES')
 else:
  print('NO')

t=int(input())
for i in range(t):
 s=str(input())
 n=len(s)
 if(n<4):
  print("NO")
 elif(s[n-4]!='0' and s[n-3]=='0' and s[n-2]=='0' and s[n-1]=='0'):
  print("YES")
 else:
  print("NO")

# cook your dish here
t=int(input())
for i in range(t):
 s=str(input())
 n=len(s)
 if(n<4):
  print("NO")
 elif(s[n-4]!='0' and s[n-3]=='0' and s[n-2]=='0' and s[n-1]=='0'):
  print("YES")
 else:
  print("NO")

t=int(input())
l=[]
for i in range(t):
 s=str(input())
 le=len(s)
 if(le<4):
  l.append("NO")
 elif(s[le-1]=='0' and s[le-2]=='0' and s[le-3]=='0' and s[le-4]=='1'):
  l.append("YES")
 else:
  l.append("NO")
for i in l:
 print(i)
  


t=int(input())
l=[]
for i in range(t):
 s=str(input())
 le=len(s)
 if(le<4):
  l.append("NO")
 elif(s[le-1]=='0' and s[le-2]=='0' and s[le-3]=='0' and s[le-4]=='1'):
  l.append("YES")
 else:
  l.append("NO")
for i in l:
 print(i)
  


# cook your dish here
t = int(input())
for i in range(t):
 n = input()
 l= len(n)
 if(len(n) < 4 ):
  print("NO")
 elif(n[l-1]=='0' and n[l-2]=='0' and n[l-3]=='0' and n[l-4]=='1'):
  print("YES")
 else:
  print("NO")

for i in range(int(input())):
 s=input()
 l=list(s)
 if(len(l)>=4):
  if(s[-4:]=="1000"):
   print("YES")
  else:
   print("NO")
 else:
  print("NO")

for _ in range(int(input())):
 s=input()
 if len(s)>=4:
  if(s[-4:]=="1000"):
   print("YES")
  else:
   print("NO")
 else:
  print("NO")

# cook your dish here
for e in range(int(input())):
 s = input()
 if len(s) >= 4:
  if(s[-4::] == '1000'):
   print('YES')
  else:
   print('NO')
 else:
  print('NO')

# cook your dish here
def __starting_point():
 for _ in range(int(input())):
  binstr = input()
  if binstr.endswith("1000"):
   print("YES")
  else:
   print("NO")
__starting_point()

t=int(input())
for i in range(t):
 s=input()
 if(len(s)<4):
  print("NO")
 elif(s[-4:]!="1000"):
  print("NO")
 else:
  print("YES")
 


from sys import stdin

for _ in range(int(stdin.readline())):
 s = stdin.readline().strip()
 cond = True
 n = len(s)
 state = 1
 for i in range(n):
  #print("Start", state)
  if s[i] == '0':
   if state != 1 or state != 5:
    state += 1
   elif state == 5:
    state -= 4
  else:
   if state != 2:
    state = 2
  #print("End", state)
 if state == 5:
  print("YES")
 else:
  print("NO")


for _ in range(int(input())):
 n=input()
 if(len(n)>=4):
  if(n[-4:]=="1000"):
   print("YES")
  else:
   print("NO")
 else:
  print("NO")


# cook your dish here
t=int(input())
for i in range(t):
 s=input()
 if len(s)>3:
  if s[-1]=='0' and s[-2]=='0' and s[-3]=='0' and s[-4]=='1':
   print("YES")
  else:
   print("NO")
 else:
  print("NO")


t=int(input())
for _ in range(t):
 s=input()
 if len(s)>=4:
  x=s[-4]+s[-3]+s[-2]+s[-1]
  if x=='1000':
   print('YES')
  else:
   print('NO')
 else:
  print('NO')


graph = [
 {"0":0,"1":1},
 {"1":1,"0":2},
 {"0":3,"1":1},
 {"1":1,"0":4},
 {"1":1,"0":0}
]
for i in range(0,int(input())):
 S=input()
 N=len(S)
 currentIndex=0
 for i in range(0,N):
  currentIndex=graph[currentIndex][S[i]]
 if currentIndex==4:
  print("YES")
 else:
  print("NO")




t = int(input())
while t>0:
 t -= 1
 s = input()
 if len(s)<4:
  print('NO')
  continue
 if(s[-4:]!='1000'):
  print('NO')
 else:
  print('YES')

t=int(input())
for _ in range(t):
 n=input()
 if len(n)<4:
  print("NO")
 else:
  if n[-1]=='0' and n[-2]=='0' and n[-3]=='0' and n[-4]=='1':
   print("YES")
  else:
   print("NO")


# cook your dish here
def change_of_state(state,cur_no):
 if cur_no==1:
  if state=="R":state = "B"
  elif state=="B":state = "B"
  elif state=="Y":state = "B"
  elif state=="P":state = "B"
  elif state=="G":state = "B"
 else:
  if state=="R":state = "R"
  elif state=="B":state = "Y"
  elif state=="Y":state = "P"
  elif state=="P":state = "G"
  elif state=="G":state = "R"
 return state
for _ in range(int(input())):
 s = str(input())
 state = "R"
 for i in range(len(s)):state = change_of_state(state,int(s[i]))
 if state=="G":print("YES")
 else:print("NO")

# cook your dish here
T = int(input())

for _ in range(T):
 s = input()
 if(len(s)>3):
  g = s[::-1]
  if(g[0:4] == "0001"):
   print("YES")
  else:
   print("NO")
 else:
  print("NO")

import math

g = {
 1 : (1,2),
 2 : (3,2),
 3 : (4,2),
 4 : (5,2),
 5 : (1,2)
}

t = int(input().strip())

for tt in range(t):

 str = input().strip()
 v = 1

 for j in range(len(str)):
  if str[j] == '0':
   v = g[v][0]
  else:
   v = g[v][1]

 if v==5:
  print('YES')
 else:
  print('NO')

for _ in range(int(input())):
 s=input()
 if(len(s)<4):
  print("NO")
 else:
  i=len(s)
  if(s[i-4]=='1' and s[i-3]=='0' and s[i-2]=='0' and s[i-1]=='0'):
   print("YES")
  else:
   print("NO")