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: MEDIUM
Tags: Graph algorithms

Constructive algorithms

Complete search

Data structures

Ad-hoc
Skill types: Data structures

Complete search

Starter code:

Solutions:
t = int(input())
for i in range(t):
	string = input()
	place = 'R'
	for j in range(len(string)):
		if place == 'R':
			if string[j] == '1':
				place = 'B'
		elif place == 'B':
			if string[j] == '0':
				place = 'Y'
		elif place == 'Y':
			if string[j] == '1':
				place = 'B'
			elif string[j] == '0':
				place = 'P'
		elif place == 'P':
			if string[j] == '1':
				place = 'B'
			elif string[j] == '0':
				place = 'G'
		elif place == 'G':
			if string[j] == '1':
				place = 'B'
			elif string[j] == '0':
				place = 'R'
	if place == 'G':
		print('YES')
	else:
		print('NO')


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


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):
		if s[i] == '0':
			if state != 1 or state != 5:
				state += 1
			elif state == 5:
				state -= 4
		elif state != 2:
			state = 2
	if state == 5:
		print('YES')
	else:
		print('NO')


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')


for i in range(int(input())):
	s = input()
	print('YES') if s.endswith('1000') 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)


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')


from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	ed = [[0, 1], [2, 1], [3, 1], [4, 1], [0, 1]]
	st = ip()
	p = 0
	for i in range(len(st)):
		p = ed[p][int(st[i])]
	if p == 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')


for _ in range(int(input())):
	map = [[0, 1], [2, 1], [3, 1], [4, 1], [0, 1]]
	path = input()
	curr = 0
	for p in path:
		curr = map[curr][int(p)]
	if curr == 4:
		print('YES')
	else:
		print('NO')


path = {'R0': 'R', 'R1': 'B', 'B1': 'B', 'B0': 'Y', 'Y1': 'B', 'Y0': 'P', 'P1': 'B', 'P0': 'G', 'G1': 'B', 'G0': 'R'}
T = int(input())
for _ in range(T):
	s = input()
	current = 'R'
	for c in s:
		current = path[current + c]
	print('YES' if current == 'G' else 'NO')


def state(country, roa):
	road = int(roa)
	if country == 'red':
		if road == 0:
			return 'red'
		else:
			return 'blue'
	elif country == 'blue':
		if road == 1:
			return 'blue'
		else:
			return 'yellow'
	elif country == 'yellow':
		if road == 0:
			return 'pink'
		else:
			return 'blue'
	elif country == 'pink':
		if road == 0:
			return 'green'
		else:
			return 'blue'
	elif country == 'green':
		if road == 1:
			return 'blue'
		else:
			return 'red'
for _ in range(int(input())):
	s = input()
	c = 'red'
	for i in range(len(s)):
		c = state(c, s[i])
	if c == 'green':
		print('YES')
	else:
		print('NO')


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'
	elif 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')


t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	if l >= 4:
		if s.endswith('1000'):
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for case in range(int(input())):
	inp = input()
	if inp.endswith('1000'):
		print('YES')
	else:
		print('NO')


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


n = int(input())
for i in range(n):
	s = input()
	j = len(s) - 1
	if j > 2:
		if s[j - 3] == '1' and s[j - 2] == '0' and (s[j - 1] == '0') and (s[j] == '0'):
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	a = input()
	d = {'q00': 'q0', 'q01': 'q1', 'q11': 'q1', 'q10': 'q2', 'q21': 'q1', 'q20': 'q3', 'q31': 'q1', 'q30': 'q4', 'q41': 'q1', 'q40': 'q0'}
	g = 'q0'
	for i in a:
		g += i
		g = d[g]
	if g == 'q4':
		print('YES')
	else:
		print('NO')


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


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')


t = int(input())
while t > 0:
	t = t - 1
	s = input()
	a = [int(i) for i in s]
	if len(a) < 4:
		print('NO')
		continue
	sample = ['r0r', 'r1b', 'b1b', 'b0y', 'y1b', 'y0p', 'p0g', 'p1b', 'g1b', 'g0b']
	curr_state = 'r'
	next_state = ''
	k = 0
	z = 0
	for i in a:
		z += 1
		tran_val = i
		for j in sample:
			if curr_state == j[0] and tran_val == int(j[1]):
				next_state = j[2]
				break
		curr_state = next_state
		if curr_state == 'g' and z == len(a):
			print('YES')
			k = 1
			break
	if k == 0:
		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')


n = int(input())
for i in range(n):
	l = input()
	if len(l) > 3:
		if l[-1] == '1':
			print('NO')
		elif l[-2] == '0' and l[-3] == '0' and (l[-4] == '1'):
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	binstr = input()
	if binstr.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')


a = [[0 for j in range(2)] for i in range(6)]
a[1][0] = 1
a[1][1] = 2
a[2][1] = 2
a[2][0] = 3
a[3][0] = 4
a[3][1] = 2
a[4][0] = 5
a[4][1] = 2
a[5][0] = 1
a[5][1] = 2
for _ in range(int(input())):
	s = input()
	cur = 1
	for i in s:
		cur = a[cur][int(i)]
	if cur == 5:
		print('YES')
	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')


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')


def main():
	t = int(input())
	for _ in range(t):
		sx = input()
		if sx[-4:] == '1000':
			print('YES')
		else:
			print('NO')
main()


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')


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


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	s = input()
	n = len(s)
	if n >= 4 and s[n - 4:] == '1000':
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	currnode = 'red'
	for i in s:
		if currnode == 'red':
			if i == '1':
				currnode = 'blue'
		elif currnode == 'blue':
			if i == '0':
				currnode = 'yellow'
		elif currnode == 'yellow':
			if i == '0':
				currnode = 'pink'
			else:
				currnode = 'blue'
		elif currnode == 'pink':
			if i == '0':
				currnode = 'green'
			else:
				currnode = 'blue'
		elif currnode == 'green':
			if i == '0':
				currnode = 'red'
			else:
				currnode = 'blue'
	if currnode == 'green':
		print('YES')
	else:
		print('NO')


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


(t1, t2) = (1, 2)
t = 0
for _ in range(int(input())):
	a = input()
	temp = 'red'
	for i in a:
		if temp == 'red':
			if i == '1':
				temp = 'blue'
		elif temp == 'blue':
			if i == '0':
				temp = 'yellow'
		elif temp == 'yellow':
			if i == '0':
				temp = 'pink'
			else:
				temp = 'blue'
		elif temp == 'pink':
			if i == '0':
				temp = 'green'
			else:
				temp = 'blue'
		elif temp == 'green':
			if i == '0':
				temp = 'red'
			else:
				temp = 'blue'
	if temp == 'green':
		print('YES')
	else:
		print('NO')


def makeAdj():
	dic = {}
	dic[0, 0] = 0
	dic[0, 1] = 1
	dic[1, 0] = 2
	dic[1, 1] = 1
	dic[2, 1] = 1
	dic[2, 0] = 3
	dic[3, 0] = 4
	dic[3, 1] = 1
	dic[4, 1] = 1
	dic[4, 0] = 0
	return dic
adj = makeAdj()
t = int(input())
for i in range(t):
	s = str(input())
	node = 0
	for j in s:
		node = adj[node, int(j)]
	if node == 4:
		print('YES')
	else:
		print('NO')


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


t = int(input())
i = 0
while i < t:
	s = input()
	y = s[-4:]
	if y == '1000':
		print('YES')
	else:
		print('NO')
	i = i + 1


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')


def path(a):
	a = [int(i) for i in a]
	color = 'red'
	for i in a:
		if color == 'red':
			if i == 1:
				color = 'blue'
			elif i == 0:
				color = 'red'
		elif color == 'blue':
			if i == 1:
				color = 'blue'
			elif i == 0:
				color = 'yellow'
		elif color == 'yellow':
			if i == 1:
				color = 'blue'
			elif i == 0:
				color = 'pink'
		elif color == 'pink':
			if i == 1:
				color = 'blue'
			elif i == 0:
				color = 'green'
		elif color == 'green':
			if i == 1:
				color = 'blue'
			elif i == 0:
				color = 'red'
	return color == 'green'
for i in range(int(input())):
	if path(input()):
		print('YES')
	else:
		print('NO')


graph = []
for i in range(0, 5):
	l = []
	for j in range(0, 2):
		l.append(0)
	graph.append(l)
graph[0][0] = 0
graph[0][1] = 1
graph[1][0] = 2
graph[1][1] = 1
graph[2][0] = 3
graph[2][1] = 1
graph[3][0] = 4
graph[3][1] = 1
graph[4][0] = 0
graph[4][1] = 1
n = int(input())
while n:
	string = input()
	pos = 0
	for i in string:
		pos = graph[pos][int(i)]
	if pos == 4:
		print('YES')
	else:
		print('NO')
	n -= 1


from collections import defaultdict
t = int(input())
for _ in range(t):
	s = input()
	graph = [[0] * 2 for i in range(6)]
	graph[1][0] = 1
	graph[1][1] = 2
	graph[2][0] = 3
	graph[2][1] = 2
	graph[3][0] = 4
	graph[3][1] = 2
	graph[4][0] = 5
	graph[4][1] = 2
	graph[5][0] = 1
	graph[5][1] = 2
	c = 1
	for i in s:
		c = graph[c][int(i)]
	if c == 5:
		print('YES')
	else:
		print('NO')


def next(c, n):
	if n == '1':
		return 'B'
	elif c == 'R':
		return 'R'
	elif c == 'B':
		return 'Y'
	elif c == 'Y':
		return 'P'
	elif c == 'P':
		return 'G'
	else:
		return 'R'
for i in range(int(input())):
	string = input()
	c = 'R'
	for i in range(len(string)):
		n = string[i]
		c = next(c, n)
	if c == 'G':
		print('YES')
	else:
		print('NO')


T = int(input())
R = 'R'
G = 'G'
B = 'B'
Y = 'Y'
P = 'P'
Z = '0'
O = '1'
A = {}
A[R] = {}
A[R][Z] = R
A[R][O] = B
A[B] = {}
A[B][Z] = Y
A[B][O] = B
A[Y] = {}
A[Y][Z] = P
A[Y][O] = B
A[P] = {}
A[P][Z] = G
A[P][O] = B
A[G] = {}
A[G][Z] = R
A[G][O] = B
for t in range(T):
	s = input()
	c = R
	for i in s:
		c = A[c][i]
	if c == G:
		print('YES')
	else:
		print('NO')


from numpy import *
for t in range(int(input())):
	s = input()
	city = array([[0, 1, -1, -1, -1], [-1, 1, 0, -1, -1], [-1, 1, -1, 0, -1], [-1, 1, -1, -1, 0], [0, 1, -1, -1, -1]])
	k = 0
	i = 0
	flag = 0
	while k < len(s):
		for j in range(5):
			if k == len(s) - 1 and i == 3 and (j == 4):
				flag = 1
				k += 1
				break
			elif city[i][j] == int(s[k]):
				i = j
				k += 1
				break
	if flag == 0:
		print('NO')
	elif flag == 1:
		print('YES')


import collections as clts
import math
import heapq

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def lcm(x, y):
	return int(x / gcd(x, y) * y)
for _ in range(int(input())):
	graph = {'R': ['R', 'B'], 'B': ['Y', 'B'], 'Y': ['P', 'B'], 'P': ['G', 'B'], 'G': ['R', 'B']}
	S = input()
	curr = 'R'
	for edge in S:
		curr = graph[curr][int(edge)]
	if curr != 'G':
		print('NO')
	else:
		print('YES')


d = {'red': {'0': 'red', '1': 'blue'}, 'blue': {'0': 'yellow', '1': 'blue'}, 'yellow': {'0': 'violet', '1': 'blue'}, 'violet': {'0': 'green', '1': 'blue'}, 'green': {'0': 'red', '1': 'blue'}}
for _ in range(int(input())):
	s = input()
	c = 'red'
	f = 0
	for i in s:
		c = d[c][i]
	if c == 'green':
		print('YES')
	else:
		print('NO')


st = dict()
st['R'] = ['R', 'B']
st['B'] = ['Y', 'B']
st['Y'] = ['P', 'B']
st['P'] = ['G', 'B']
st['G'] = ['R', 'B']
tn = int(input())
for _ in range(tn):
	si = input()
	cs = 'R'
	for ch in si:
		cs = st[cs][int(ch)]
	if cs == 'G':
		print('YES')
	else:
		print('NO')


import sys
import math
read = lambda : list(map(int, sys.stdin.readline().strip().split()))
dfa = [[0, 1], [2, 1], [3, 1], [4, 1], [0, 1]]

def solve(s):
	cur = 0
	for i in range(len(s)):
		if s[i] == '1':
			cur = dfa[cur][1]
		else:
			cur = dfa[cur][0]
	if cur == 4:
		return True
	return False
for _ in range(int(input())):
	s = input()
	ans = solve(s)
	if ans:
		print('YES')
	else:
		print('NO')


T = int(input())
l = [[0, 1], [2, 1], [3, 1], [4, 1], [0, 1]]
for _ in range(T):
	s = input()
	a = 0
	for i in s:
		x = int(i)
		a = l[a][x]
	if a == 4:
		print('YES')
	else:
		print('NO')


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


adj = [[0, 1], [2, 1], [3, 1], [4, 1], [0, 1]]
T = int(input())
for _ in range(T):
	L = list(input())
	M = [int(x) for x in L]
	initial = 0
	for i in range(len(M)):
		a = int(M[i])
		initial = adj[initial][a]
	if initial == 4:
		print('YES')
	else:
		print('NO')


read = lambda : map(int, input().split(' '))
for I in range(int(input())):
	s = input()
	n = len(s)
	if n < 4:
		print('NO')
		continue
	if s[n - 1] == '0' and s[n - 2] == '0' and (s[n - 3] == '0') and (s[n - 4] == '1'):
		print('YES')
	else:
		print('NO')


def Helper(index, S, adj, root):
	if index == len(S) and root == 4:
		return True
	if index >= len(S):
		return False
	ans = False
	for node in adj[root]:
		if node[1] == S[index]:
			ans = ans | Helper(index + 1, S, adj, node[0])
		else:
			pass
	return ans

def function(S, adj):
	if len(S) > 3 and S[len(S) - 4:] == '1000':
		return 'YES'
	return 'NO'

def createADJ():
	adj = [[] for i in range(5)]
	adj[0] = [(0, '0'), (1, '1')]
	adj[1] = [(1, '1'), (2, '0')]
	adj[2] = [(1, '1'), (3, '0')]
	adj[3] = [(4, '0'), (1, '1')]
	adj[4] = [(0, '0'), (1, '1')]
	return adj

def main():
	T = int(input())
	for _ in range(T):
		adj = createADJ()
		S = input()
		val = function(S, adj)
		print(val)
main()