You are given a string $s$, consisting only of characters '0' or '1'. Let $|s|$ be the length of $s$.

You are asked to choose some integer $k$ ($k > 0$) and find a sequence $a$ of length $k$ such that:

$1 \le a_1 < a_2 < \dots < a_k \le |s|$;

$a_{i-1} + 1 < a_i$ for all $i$ from $2$ to $k$.

The characters at positions $a_1, a_2, \dots, a_k$ are removed, the remaining characters are concatenated without changing the order. So, in other words, the positions in the sequence $a$ should not be adjacent.

Let the resulting string be $s'$. $s'$ is called sorted if for all $i$ from $2$ to $|s'|$ $s'_{i-1} \le s'_i$.

Does there exist such a sequence $a$ that the resulting string $s'$ is sorted?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Then the descriptions of $t$ testcases follow.

The only line of each testcase contains a string $s$ ($2 \le |s| \le 100$). Each character is either '0' or '1'.


-----Output-----

For each testcase print "YES" if there exists a sequence $a$ such that removing the characters at positions $a_1, a_2, \dots, a_k$ and concatenating the parts without changing the order produces a sorted string.

Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).


-----Examples-----

Input
5
10101011011
0000
11111
110
1100
Output
YES
YES
YES
YES
NO


-----Note-----

In the first testcase you can choose a sequence $a=[1,3,6,9]$. Removing the underlined letters from "10101011011" will produce a string "0011111", which is sorted.

In the second and the third testcases the sequences are already sorted.

In the fourth testcase you can choose a sequence $a=[3]$. $s'=$ "11", which is sorted.

In the fifth testcase there is no way to choose a sequence $a$ such that $s'$ is sorted.

Difficulty: EASY
Tags: Dynamic programming

Complete search

Implementation

Greedy algorithms
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
from random import *
input = stdin.readline
prin = stdout.write
from random import sample
from collections import Counter, deque
from fractions import *
from math import sqrt, ceil, log2, gcd
mod = 10 ** 9 + 7

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	lk = 0
	arr = {}
	while n % 2 == 0:
		n = n // 2
		lk += 1
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		lk = 0
		cc = 0
		while n % ps == 0:
			n = n // ps
			lk += 1
	if n != 1:
		lk += 1
		return False
	return True

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def power(arr):
	listrep = arr
	subsets = []
	for i in range(2 ** len(listrep)):
		subset = []
		for k in range(len(listrep)):
			if i & 1 << k:
				subset.append(listrep[k])
		subsets.append(subset)
	return subsets

def pda(n):
	list = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				list.append(i)
			else:
				list.append(n // i)
				list.append(i)
	return list

def dis(xa, ya, xb, yb):
	return sqrt((xa - xb) ** 2 + (ya - yb) ** 2)

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

def ilist():
	return [int(x) for x in input().strip().split()]

def islist():
	return list(map(str, input().split().rstrip()))

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

def google(test, ans):
	return 'Case #' + str(test) + ': ' + str(ans)

def overlap(x1, y1, x2, y2):
	if x2 > y1:
		return y1 - x2
	if y1 > y2:
		return y2 - x2
	return y1 - x2
t = int(input())
for p in range(t):
	s = input()
	n = len(s)
	one = 0
	zero = 0
	cc = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			if s[i] == '1':
				one = 1
			elif one == 1:
				cc = 0
				break
			else:
				zero = 1
	if cc:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	(ok, ones) = (True, False)
	for i in range(1, len(s)):
		if not ones and s[i - 1] == s[i] and (s[i] == '1'):
			ones = True
		elif ones and s[i - 1] == s[i] and (s[i] == '0'):
			ok = False
			break
	print('YES' if ok else 'NO')


for _ in range(int(input())):
	case = input()
	i = case.find('11')
	j = case.rfind('00')
	if i < j and i != -1 and (j != -1):
		print('NO')
	else:
		print('YES')


t = int(input())
for p in range(t):
	n = input()
	if n.find('11') == -1 or n.find('00') == -1:
		print('YES')
	elif n.find('00', n.find('11') + 1) == -1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	(l, r) = (s.rfind('00'), s.find('11'))
	if l != -1 and r != -1:
		if l < r:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
while t:
	a = input()
	one = a.find('11')
	zero = a.rfind('00')
	if one != -1 and zero != -1 and (one < zero):
		print('NO')
	else:
		print('YES')
	t -= 1


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt
import bisect
import copy
from itertools import combinations
import sys

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	s = input()
	flag = 0
	for i in range(len(s)):
		ind = i
		(c, d) = ([], [])
		for j in range(ind):
			if s[j] == '1':
				c.append(j)
		for j in range(ind + 1, len(s)):
			if s[j] == '0':
				d.append(j)
		m = 0
		for i in range(1, len(c)):
			if c[i] - c[i - 1] < 2:
				m = 1
				break
		for i in range(1, len(d)):
			if d[i] - d[i - 1] < 2:
				m = 1
				break
		if m == 0:
			flag = 1
			break
	if flag == 0:
		print('NO')
	else:
		print('YES')


def fun(c):
	if c == '0':
		for i in range(n - 1, 0, -1):
			if c == s[i] and s[i] == s[i - 1]:
				return i
		return -1
	else:
		for i in range(1, n):
			if c == s[i] and s[i] == s[i - 1]:
				return i
		return n
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	if fun('0') < fun('1'):
		print('YES')
	else:
		print('NO')


tc = int(input())
for t in range(tc):
	seq = input()
	rmost00 = seq.rfind('00')
	lmost11 = seq.find('11')
	if rmost00 >= 0 and lmost11 >= 0 and (rmost00 > lmost11):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	if '11' in s and '00' in s and (s.index('11') < s.rfind('00')):
		print('NO')
	else:
		print('YES')


import math
import sys
t = int(input())
for gp in range(t):
	s = input()
	index1 = s.find('11')
	index2 = s.rfind('00')
	if index1 != -1 and index2 != -1 and (index1 < index2):
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	s = input()
	if '11' in s:
		i = s.index('11')
		a = s[i:]
		if '00' in a:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	print('YES' if s.find('00', max(s.find('11'), 0)) == -1 or s.find('11') == -1 else 'NO')


for _ in range(int(input())):
	a = input()
	(one, zero, n, b) = (0, 0, len(a), 0)
	for i in range(0, n - 1):
		if a[i] == '1':
			if a[i + 1] == '1':
				one = 1
				b = i
				break
	for j in range(b, n - 1):
		if a[j] == '0':
			if a[j + 1] == '0':
				zero = 1
				break
	if one == 1 and zero == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	x = input()
	try:
		y = x.index('11')
		z = len(x) - x[::-1].index('00') - 2
	except:
		print('Yes')
		continue
	if y < z:
		print('No')
	else:
		print('Yes')


t = int(input())
for _ in range(t):
	s = input()
	ss = s.replace('10', '')
	print('YES' if ss == ''.join(sorted(ss)) else 'NO')


for _ in range(int(input())):
	string = input()
	oneIdx = None
	try:
		oneIdx = string.index('11')
	except Exception:
		pass
	zeroIdx = None
	try:
		zeroIdx = len(string) - 1 - string[::-1].index('00')
	except Exception:
		pass
	if oneIdx == None or zeroIdx == None:
		print('YES')
	elif oneIdx > zeroIdx:
		print('YES')
	else:
		print('NO')


trials = int(input())
for trial in range(trials):
	n = input()
	if '11' in n:
		x = n.index('11')
		if '00' in n[x:]:
			print('NO')
			n = 0
	if n != 0:
		print('YES')


import sys
from collections import deque
import math
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
for _ in range(ii()):
	a = list(ip())
	fl = 0
	b = 0
	l = len(a)
	for i in range(1, l):
		if a[i] == a[i - 1] and fl == 0:
			if a[i] == '1':
				fl = 1
		elif a[i] == a[i - 1] and fl == 1 and (a[i] == '0'):
			b = 1
			break
	if b:
		print('NO')
	else:
		print('YES')


from __future__ import division, print_function
import os
import sys
sys.setrecursionlimit(1000000)
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
import sys
import bisect
from collections import defaultdict
for t in range(int(input())):
	s = input()
	flag = True
	idx = -1
	idx0 = -1
	for i in range(len(s) - 1):
		if s[i] == '1' and s[i + 1] == '1' and flag:
			idx = i
			flag = False
		if s[i] == '0' and s[i + 1] == '0':
			idx0 = i
	if idx == -1 or idx0 == -1:
		print('YES')
		continue
	if idx < idx0:
		print('NO')
	else:
		print('YES')
main()


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	(a, b) = (-1, -1)
	if s.count('1') == n or s.count('0') == n:
		print('YES')
	else:
		a = s.find('11')
		b = s.rfind('00')
		if a == -1 or b == -1:
			print('YES')
		elif a < b:
			print('NO')
		else:
			print('YES')


def solve(s, n, can_leave, last, d):
	if n == 0:
		return True
	if (n, can_leave, last) in d:
		return d[n, can_leave, last]
	curr = int(s[n - 1])
	if curr > last and can_leave == False:
		temp = False
	elif curr > last and can_leave == True:
		temp = solve(s, n - 1, False, last, d)
	elif curr <= last and can_leave == True:
		temp = solve(s, n - 1, True, curr, d) or solve(s, n - 1, False, last, d)
	elif curr <= last and can_leave == False:
		temp = solve(s, n - 1, True, curr, d)
	d[n, can_leave, last] = temp
	return temp
for testcase in range(int(input())):
	s = input()
	p = solve(s, len(s), True, float('inf'), {})
	if p:
		print('YES')
	else:
		print('NO')


N = int(input())
for t in range(N):
	s = input()
	M = s.find('11')
	if M == -1:
		print('YES')
		continue
	if s[M:].find('00') != -1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	n = len(s)
	flag = 0
	for i in range(n - 1):
		if flag == 0:
			if s[i] == '1' and s[i + 1] == '1':
				flag = 1
		elif flag == 1:
			if s[i] == '0' and s[i + 1] == '0':
				flag = 2
		else:
			break
	if flag == 2:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	s = input()
	if '00' in s[s.find('11'):]:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	ss = input()
	flag = 0
	n = len(ss)
	for i in range(n - 1):
		if ss[i] == '1' and ss[i + 1] == '1':
			break
	for j in range(i + 1, n - 1):
		if ss[j] == '0' and ss[j + 1] == '0':
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s1 = input()
	if '11' in s1 and '00' in s1 and (s1.find('11') < s1.rfind('00')):
		print('NO')
	else:
		print('YES')


t = int(input())
for z in range(t):
	s = input()
	one = False
	zero = False
	for i in range(1, len(s), 1):
		if one == False and (s[i] == '1' and s[i - 1] == '1'):
			one = True
		if one == True and zero == False and (s[i] == '0' and s[i - 1] == '0'):
			zero = True
		if one and zero:
			break
	if one == True and zero == True:
		print('NO')
	else:
		print('YES')


T = int(input())
while T:
	T -= 1
	s = input()
	k = 0
	for i in range(1, len(s)):
		if k == 0 and s[i] == s[i - 1] == '1':
			k += 1
		if k == 1 and s[i] == s[i - 1] == '0':
			k += 1
			break
	if k == 2:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	if '11' not in s or '00' not in s:
		print('YES')
		continue
	b = s.index('11')
	a = len(s) - s[::-1].index('00') - 2
	if b < a:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()
	try:
		i = s.index('11') + 2
		if '00' in s[i:]:
			print('NO')
		else:
			print('YES')
	except:
		print('YES')


for _ in range(int(input())):
	n = input()
	d = n.find('11')
	f = n.rfind('00')
	if d != -1 and f != -1 and (d < f):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	if '11' not in s or '00' not in s:
		print('YES')
		continue
	if s.find('11') < s.rfind('00'):
		print('NO')
	else:
		print('YES')


import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
for t in range(T):
	s = lines[t + 1].strip()
	L = len(s)
	satisfy = True
	pairOne = False
	ind = -1
	pairZero = False
	for i in range(1, L):
		if s[i] == '1' and s[i - 1] == '1':
			pairOne = True
			ind = i
			break
	if pairOne:
		for i in range(ind + 2, L):
			if s[i] == '0' and s[i - 1] == '0':
				pairZero = True
				break
	if pairZero:
		print('NO')
	else:
		print('YES')


import sys
import io, os
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = str(input().rstrip())
	n = len(s)
	X = []
	Y = []
	for (i, c) in enumerate(s):
		if c == '0':
			X.append(i)
		else:
			Y.append(i)
	if len(X) <= 1 or len(Y) <= 1:
		print('YES')
		continue
	for k in range(n):
		flag = True
		for j in range(len(X) - 1):
			if X[j] >= k and X[j] + 1 == X[j + 1]:
				flag = False
				break
		for j in range(len(Y) - 1):
			if Y[j + 1] < k and Y[j] + 1 == Y[j + 1]:
				flag = False
				break
		if flag:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	c1 = s.find('11')
	c2 = s.rfind('00')
	if c1 >= 0 and c2 >= 0 and (c1 < c2):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = input()
	a = n.rfind('00')
	b = n.find('11')
	if a < 0 or b < 0 or b > a:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(0, t, 1):
	s = str(input())
	a = s.find('11')
	b = s.rfind('00')
	if a < b and a != -1 and (b != -1):
		print('NO')
	else:
		print('YES')


t = int(input())

def slv(s):
	pts = s.split('11')
	for pt in pts[1:]:
		if '00' in pt:
			return False
	return True
for _ in range(t):
	s = input()
	if slv(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for j in range(0, t):
	inp = input()
	m = False
	adj_z = False
	adj_o = False
	n = len(inp)
	for i in range(1, n):
		if inp[i] == inp[i - 1]:
			if adj_o == True:
				if inp[i] == '0':
					m = True
			elif inp[i] == '1':
				adj_o = True
			else:
				adj_z = True
	if m == True:
		print('NO')
	else:
		print('YES')


t = int(input())
results = []

def find_doublez(s, v):
	for i in range(1, len(s)):
		if s[-i:-i - 2:-1] == [v, v]:
			return i
	return 0
for i in range(t):
	s = input()
	s = [int(c) for c in s]
	dbz = find_doublez(s, 0)
	if dbz == 0:
		results.append('yes')
	else:
		dbo = find_doublez(s[:-dbz - 1], 1)
		if dbo:
			results.append('no')
		else:
			results.append('yes')
for i in range(t):
	print(results.pop(0))


import collections
import sys

def localmin():

	def recur(l, low, high, n):
		mid = (low + high) // 2
		while low != high:
			if l[mid] == 0 or l[mid - 1] == 0 or l[mid + 1] == 0:
				mid += 1
				continue
			if mid > 0 and l[mid - 1] < l[mid] or (mid < n - 1 and l[mid] > l[mid + 1]):
				low = mid + 1
				mid = (low + high) // 2
			elif mid < n - 1 and l[mid] < l[mid + 1] or (mid > 0 and l[mid - 1] > l[mid]):
				high = mid
				mid = (low + high) // 2
		return low + 1
	num = int(input())
	l = [0] * num
	for i in range(1, num + 1):
		print('?', i, sep=' ')
		sys.stdout.flush()
		l[int(input()) - 1] = i
		if i == 101:
			break
	return '! ' + str(recur(l, 0, len(l) - 1, len(l) - 1))

def painting():
	num = int(input())
	l = input().split()
	pos = 0
	c = 0
	l1last = ''
	llast = ''
	while pos < num:
		if l[pos] != llast:
			llast = l[pos]
			pos1 = pos + 1
			c += 1
		while pos1 < num and l[pos1] == llast:
			pos1 += 1
		try:
			if pos1 - pos != 1 and l[pos1] != l1last:
				c += 1
				l1last = l[pos1 - 1]
		except:
			return c + 1
		pos = pos1
	return c

def arena():
	case = int(input())
	for _ in range(case):
		num = int(input())
		l = sorted(list(map(int, input().split())))
		(minn, *l) = l
		for (i, v) in enumerate(l):
			if v > minn:
				print(len(l) - i)
				break
		else:
			print(0)

def catcycle():
	case = int(input())
	for _ in range(case):
		(spots, hour) = map(int, input().split())
		if spots % 2:
			a = spots
			b = 1
			hour %= spots * (spots // 2) + spots // 2 - 1
			for i in range(1, hour):
				a -= 1
				if (b + 1) % spots == a:
					b += 2
				else:
					b += 1
				if b > spots:
					b = b % spots
				if a < 1:
					a = spots
			print(b)
		else:
			spot = hour % spots
			print(spot if spot else spots)

def vanyafence():
	(f, maxh) = map(int, input().split())
	res = 0
	for i in input().split():
		if int(i) > maxh:
			res += 1
		res += 1
	return res

def antonanddanik():
	num = input()
	s = input()
	ac = s.count('A')
	dc = s.count('D')
	if dc == ac:
		return 'Friendship'
	return 'Anton' if ac > dc else 'Danik'

def weight():
	(a, b) = map(int, input().split())
	for i in range(1, 10000):
		a *= 3
		b *= 2
		if a > b:
			return i

def petyarain():
	num = int(input())
	l = input().split()
	ans = 0
	for i in range(num):
		c = 1
		for i1 in range(i - 1, -1, -1):
			if int(l[i1]) > int(l[i1 + 1]):
				break
			c += 1
		for i1 in range(i + 1, num):
			if int(l[i1 - 1]) < int(l[i1]):
				break
			c += 1
		ans = max(ans, c)
	return ans

def findcrim():
	(num, inp) = map(int, input().split())
	thed = min(inp - 1, num - inp)
	l = list(map(int, input().split()))
	c = 0
	for i in range(1, thed + 1):
		if l[inp - i - 1] and l[inp + i - 1]:
			c += 2
	if thed == inp - 1:
		c += l[thed * 2 + 1:].count(1)
	else:
		c += l[:inp - thed - 1].count(1)
	return c if not l[inp - 1] else c + 1

def burglarandmatch():
	(maxn, boxs) = map(int, input().split())
	l = sorted([list(map(int, input().split())) for _ in range(boxs)], key=lambda x: x[1], reverse=True)
	ans = 0
	for i in l:
		if maxn - i[0] < 0:
			ans += maxn * i[1]
			break
		ans += i[0] * i[1]
		maxn -= i[0]
	return ans

def caisajump():
	num = int(input()) + 1
	l = [0] + list(map(int, input().split()))
	energy = 0
	ans = 0
	for i in range(num - 1):
		ne = l[i] - l[i + 1]
		energy += ne
		if energy < 0:
			ans -= energy
			energy = 0
	return ans

def tictac():

	def dicide(l):
		black = False
		white = False
		for i in l:
			if i.count('X') == 3:
				if black:
					return False
				black = True
			elif i.count('O') == 3:
				if white:
					return False
				white = True
		for i in range(len(l)):
			bc = 0
			wc = 0
			for i1 in range(len(l)):
				if l[i1][i] == 'X':
					bc += 1
				elif l[i1][i] == 'O':
					wc += 1
			if bc == 3:
				if black:
					return False
				black = True
			elif wc == 3:
				if white:
					return False
				white = True
		bc = 0
		wc = 0
		for i in range(3):
			if l[i][i] == 'X':
				bc += 1
			if l[i][i] == 'O':
				wc += 1
		if bc == 3:
			if black:
				return False
			black = True
		elif wc == 3:
			if white:
				return False
			white = True
		if l[0][2] == 'X' and l[1][1] == 'X' and (l[2][0] == 'X'):
			if black:
				return False
			black = True
		elif l[0][2] == 'O' and l[1][1] == 'O' and (l[2][0] == 'O'):
			if white:
				return False
			white = True
		return False if white and black else True
	num = int(input())
	for _ in range(num):
		xc = 0
		oc = 0
		lar = []
		for i in range(3):
			l = input()
			xc += l.count('X')
			oc += l.count('O')
			lar.append(l)
		if oc > xc or not dicide(lar) or oc < xc - 1:
			print('no')
		else:
			print('yes')
		if _ != num - 1:
			s = input()
from copy import deepcopy

def change(pos, pos1, l, c):
	return l[:pos] + [l[pos][:pos1] + c + l[pos][pos1 + 1:]] + l[pos + 1:]

def tictac1():

	def dicide(l):
		for i in l:
			if i.count('X') == 3:
				return True
			elif i.count('O') == 3:
				return True
		for i in range(len(l)):
			bc = 0
			wc = 0
			for i1 in range(len(l)):
				if l[i1][i] == 'X':
					bc += 1
				elif l[i1][i] == 'O':
					wc += 1
			if bc == 3:
				return True
			elif wc == 3:
				return True
		bc = 0
		wc = 0
		for i in range(3):
			if l[i][i] == 'X':
				bc += 1
			if l[i][i] == 'O':
				wc += 1
		if bc == 3:
			return True
		elif wc == 3:
			return True
		if l[0][2] == 'X' and l[1][1] == 'X' and (l[2][0] == 'X'):
			return True
		elif l[0][2] == 'O' and l[1][1] == 'O' and (l[2][0] == 'O'):
			return True
	his = set()
	todo = [[['...', '...', '...'], 'X']]
	while todo:
		(l, now) = todo.pop()
		tl = tuple(l)
		if tl not in his:
			his.add(tl)
		else:
			continue
		if dicide(l):
			continue
		if now == 'X':
			for i in range(3):
				for i1 in range(3):
					if l[i][i1] == '.':
						todo.append([change(i, i1, l, now), 'O'])
		else:
			for i in range(3):
				for i1 in range(3):
					if l[i][i1] == '.':
						todo.append([change(i, i1, l, now), 'X'])
	n = int(input())
	for i in range(n):
		print('yes' if tuple((input() for _ in range(3))) in his else 'no')
		if i != n - 1:
			input()

def tictac2():

	def dicide(l):
		for i in l:
			if '.' in i:
				break
		else:
			return True
		for i in l:
			if i.count('X') == 3:
				return True
			elif i.count('O') == 3:
				return True
		for i in range(len(l)):
			bc = 0
			wc = 0
			for i1 in range(len(l)):
				if l[i1][i] == 'X':
					bc += 1
				elif l[i1][i] == 'O':
					wc += 1
			if bc == 3:
				return True
			elif wc == 3:
				return True
		bc = 0
		wc = 0
		for i in range(3):
			if l[i][i] == 'X':
				bc += 1
			if l[i][i] == 'O':
				wc += 1
		if bc == 3:
			return True
		elif wc == 3:
			return True
		if l[0][2] == 'X' and l[1][1] == 'X' and (l[2][0] == 'X'):
			return True
		elif l[0][2] == 'O' and l[1][1] == 'O' and (l[2][0] == 'O'):
			return True
	his = set()
	todo = [[['...', '...', '...'], 'X']]
	while todo:
		(l, now) = todo.pop()
		if tuple(l) in his:
			continue
		if dicide(l):
			his.add(tuple(l))
			continue
		if now == 'X':
			for i in range(3):
				for i1 in range(3):
					if l[i][i1] == '.':
						todo.append([change(i, i1, l, now), 'O'])
		else:
			for i in range(3):
				for i1 in range(3):
					if l[i][i1] == '.':
						todo.append([change(i, i1, l, now), 'X'])
	print(his)
	while True:
		s = input()
		if s == 'end':
			break
		print('valid' if tuple([s[:3], s[3:6], s[6:9]]) in his else 'invalid')

def tictac3():
	his = {('OXX', 'O..', 'OX.'), ('X..', 'OXO', 'OXX'), ('O..', '.OX', 'XXO'), ('.OX', 'XXX', 'OO.'), ('XOX', '.XO', 'O.X'), ('OXX', 'O.X', 'OXO'), ('.OX', 'XOX', '.O.'), ('OXX', 'XX.', 'OOO'), ('X.O', 'XOO', 'OXX'), ('X.O', 'OOX', 'OXX'), ('..O', 'XOX', 'O.X'), ('...', 'O.O', 'XXX'), ('.XO', 'OO.', 'XXX'), ('OOO', 'XXO', '.XX'), ('XXX', 'OO.', 'XO.'), ('OOX', '.X.', 'X..'), ('.X.', '.XO', 'OX.'), ('OX.', 'XXX', 'O.O'), ('XXO', 'XXO', '.OO'), ('O.X', 'OXX', 'X.O'), ('OXX', 'XO.', 'OXO'), ('X.O', 'XOX', 'O..'), ('..X', 'OOO', 'X.X'), ('O.X', 'OXO', 'OXX'), ('.O.', 'XO.', 'XOX'), ('OXX', '.OO', 'XXO'), ('.O.', 'XOX', 'XO.'), ('XXX', 'O..', 'OOX'), ('XXX', 'O..', 'XOO'), ('.XO', '.XO', 'X.O'), ('X..', 'XO.', 'X.O'), ('O.O', '.XO', 'XXX'), ('.X.', 'OX.', '.XO'), ('.XX', 'OXO', 'XO.'), ('.XX', 'OXX', 'OOO'), ('X.O', 'XXX', 'O.O'), ('OOX', '.OX', 'XXO'), ('..X', 'OOX', 'OXX'), ('.XO', 'XXX', 'OO.'), ('.OO', 'XO.', 'XXX'), ('XXX', 'O.O', 'X.O'), ('XXO', '..O', '.XO'), ('.OX', 'OX.', 'XXO'), ('XXO', 'X..', 'XOO'), ('OXO', 'X.O', 'XXO'), ('XOX', 'XO.', 'OOX'), ('XO.', 'XO.', 'X..'), ('XOX', 'OX.', '.OX'), ('OOX', '.XO', 'XX.'), ('XXX', '..O', 'OOX'), ('XXX', '..O', 'XOO'), ('X.X', 'XOX', 'OOO'), ('XOO', '..O', 'XXX'), ('OOX', '..O', 'XXX'), ('XXX', '.XO', '.OO'), ('OOX', '.X.', 'XXO'), ('X.O', 'XXX', 'OO.'), ('.X.', 'OX.', 'OX.'), ('XXX', 'XO.', 'O.O'), ('OOO', 'X..', 'X.X'), ('XOO', '.X.', 'XOX'), ('OOX', '.X.', 'XOX'), ('XXX', '.O.', '..O'), ('O.X', 'O.X', 'XOX'), ('XO.', 'XXX', '.OO'), ('..O', '.O.', 'XXX'), ('O..', 'OXX', 'O.X'), ('XOO', 'XXX', '..O'), ('..X', 'OXO', 'XXO'), ('OOX', 'XXX', '..O'), ('..X', 'OOX', '..X'), ('.OX', 'OX.', 'XOX'), ('XXX', 'O.O', '.OX'), ('XXO', 'XX.', 'OOO'), ('O.X', '.OX', '.XO'), ('XXX', '.OO', 'O.X'), ('XOO', 'XOX', '.OX'), ('OXO', 'XXO', 'OXX'), ('OX.', 'XOX', 'XOO'), ('XOO', 'XXO', 'X..'), ('OOX', 'XXO', 'X..'), ('OXO', 'O.X', 'OXX'), ('.XX', 'O.X', 'OOX'), ('.OX', '.OX', 'XO.'), ('.OX', 'XXX', 'O.O'), ('OOO', 'OXX', '.XX'), ('X.O', '.XO', 'X.O'), ('XOX', 'OX.', 'XO.'), ('XXO', 'OO.', 'OXX'), ('XXO', 'X.X', 'OOO'), ('..X', '..X', 'OOX'), ('XXO', '.XO', 'XOO'), ('OXX', 'OXX', 'O.O'), ('XOO', '.XO', 'XXO'), ('XO.', 'XOX', 'X.O'), ('XOX', 'OOX', 'XO.'), ('XOO', 'X..', 'XOX'), ('XO.', '.X.', 'O.X'), ('OOO', 'XXO', 'XX.'), ('OXX', 'OXO', '.X.'), ('OOO', 'X.X', 'XOX'), ('XXX', 'OOX', 'OOX'), ('XXX', 'XOO', 'OOX'), ('X..', '.XO', 'O.X'), ('X.O', 'OX.', 'XOX'), ('OXX', 'OOO', 'XX.'), ('XXX', 'OOX', 'XOO'), ('XXX', 'XOO', 'XOO'), ('XOX', 'XOX', 'OXO'), ('O.X', 'XO.', 'X.O'), ('O.O', '...', 'XXX'), ('XOX', '.OX', '.O.'), ('XXX', 'OOX', '.O.'), ('OXO', '.XO', 'XX.'), ('XXX', 'XOO', '.O.'), ('XXX', '..O', 'OXO'), ('O.X', 'OX.', 'OX.'), ('OXX', 'O..', 'O.X'), ('X.O', 'X.X', 'XOO'), ('X.O', 'XOX', 'X.O'), ('..O', 'O..', 'XXX'), ('...', 'XXX', 'O.O'), ('..X', 'OXO', 'X..'), ('OXX', '.OX', '.OX'), ('X.O', 'OXX', '.OX'), ('OXX', 'OX.', 'XO.'), ('XXX', '.OX', 'OO.'), ('.X.', '.XX', 'OOO'), ('.XX', 'OOO', 'XXO'), ('OXX', 'OXX', 'OO.'), ('.XO', 'OX.', 'OXX'), ('.XO', 'OXO', '.XX'), ('OO.', 'XXX', 'OX.'), ('XO.', 'XO.', '.OX'), ('OOX', '..X', 'XOX'), ('OOO', 'X.X', 'XXO'), ('X.O', 'X..', 'X.O'), ('X..', 'XOX', 'XOO'), ('X.O', 'OXO', 'X.X'), ('XXO', 'OOX', 'XXO'), ('OOX', 'XXO', 'XOX'), ('XXO', 'OX.', 'O.X'), ('XOO', 'XXO', 'XOX'), ('OX.', 'OXX', 'OOX'), ('OOX', 'OX.', 'OXX'), ('.XO', 'XO.', 'OX.'), ('XXX', '.OO', 'XO.'), ('.XX', 'OXO', 'OX.'), ('XXO', 'OXO', '.X.'), ('XXX', '...', 'O.O'), ('XOO', 'XO.', 'OXX'), ('.OX', 'OXO', 'XX.'), ('XXO', 'XOX', 'XOO'), ('XXX', '.OO', '.OX'), ('.OX', 'XXX', '.OO'), ('XO.', 'X..', 'X.O'), ('XX.', 'OXO', '.OX'), ('XX.', 'XOO', 'XO.'), ('X.X', '.XO', 'OOX'), ('OOX', 'X.X', '.OX'), ('OXO', '..O', 'XXX'), ('X.X', '.XO', 'XOO'), ('XXO', 'XO.', 'OOX'), ('OXO', 'XXX', 'O..'), ('XX.', '.XO', 'OXO'), ('XXX', 'O.O', '.XO'), ('.OO', 'XOX', 'XOX'), ('XO.', 'XX.', 'OOX'), ('X.X', 'OOO', '..X'), ('O.X', '.XO', 'XXO'), ('XO.', 'XX.', 'XOO'), ('.XO', 'O.O', 'XXX'), ('...', 'OO.', 'XXX'), ('OOO', 'OXX', 'XX.'), ('OX.', 'XO.', '.XO'), ('.OO', '.XO', 'XXX'), ('XXO', 'XOO', 'XOX'), ('XXO', 'OOX', 'XOX'), ('.OX', 'O.X', '..X'), ('XXX', '.OO', '...'), ('O.X', '.XO', 'XOX'), ('OO.', '.XO', 'XXX'), ('XXX', 'O.O', 'O.X'), ('OOO', 'XX.', 'OXX'), ('XO.', 'OXO', '.XX'), ('O.X', 'XOX', '..O'), ('XOO', '.X.', 'OXX'), ('XX.', 'XOO', 'X.O'), ('OXO', 'XXX', '..O'), ('OXO', '.X.', '.X.'), ('O..', 'XOX', 'X.O'), ('XX.', 'X..', 'OOO'), ('OXO', 'XXO', 'XOX'), ('OOX', 'O.X', '.XX'), ('OXX', 'OXO', 'O.X'), ('.XO', '.OO', 'XXX'), ('XXO', 'OOX', 'O.X'), ('XXO', 'XOO', 'O.X'), ('.O.', 'XXX', 'OXO'), ('XXO', 'OXO', 'X.O'), ('XOX', 'XOO', 'X..'), ('XXX', 'OOX', '..O'), ('XXX', 'XOO', '..O'), ('...', 'XXX', 'OO.'), ('XX.', 'OX.', 'OXO'), ('.XO', '.O.', 'OXX'), ('OXX', 'OXO', 'X..'), ('O.X', 'XXO', 'XO.'), ('XXX', '.OX', 'O.O'), ('OX.', 'OXO', '.XX'), ('X.O', '.XO', '..X'), ('OOO', 'XOX', 'X.X'), ('XXO', '.X.', 'OXO'), ('X.O', 'OXO', 'XXO'), ('X.O', 'X..', 'XO.'), ('XO.', 'O.O', 'XXX'), ('.XO', 'XXO', 'XOO'), ('OO.', 'OXX', 'OXX'), ('XOX', '.XO', '.OX'), ('OX.', 'OXO', 'XX.'), ('..X', 'XOX', 'OOX'), ('OXO', 'OX.', 'XX.'), ('X..', 'X..', 'XOO'), ('XO.', 'X.O', 'X..'), ('XOO', 'XXX', '.O.'), ('O.O', 'XOX', 'OXX'), ('OOX', 'XXX', '.O.'), ('OO.', 'XXX', 'O.X'), ('XXX', '.O.', '.O.'), ('..X', 'OOO', 'XX.'), ('O.X', '.O.', 'XXO'), ('XXO', 'O.O', 'XXO'), ('..O', 'XXO', 'X.O'), ('XXX', '.O.', 'OOX'), ('.O.', '.O.', 'XXX'), ('OX.', 'XXO', 'OX.'), ('.XO', '.XO', 'OXX'), ('XXX', '.O.', 'XOO'), ('OX.', 'O.X', 'O.X'), ('O.X', 'XX.', 'XOO'), ('XXX', '...', 'OO.'), ('.OX', 'XOX', 'XOO'), ('OX.', 'O..', 'OXX'), ('O.O', 'OXX', 'OXX'), ('X.O', 'XXO', 'O.X'), ('O.X', 'OXX', 'OXO'), ('X.X', 'OOO', 'XXO'), ('X..', 'OX.', 'O.X'), ('.XO', '..O', 'XXO'), ('X.O', 'XXX', '.OO'), ('.OO', 'XXX', 'X.O'), ('OOO', 'XX.', 'XXO'), ('.O.', 'OXO', 'XXX'), ('XXO', '.XO', 'O.X'), ('.OX', 'XO.', '.OX'), ('XOX', 'OOO', '.XX'), ('X.X', '..X', 'OOO'), ('OOX', '.XX', 'X.O'), ('X.X', 'OOO', '.X.'), ('O..', 'XXX', 'OOX'), ('XOO', 'XXO', '.XO'), ('O..', 'XXX', 'XOO'), ('O.X', 'OXO', 'X.X'), ('XO.', 'XXO', 'X.O'), ('XOX', 'X.O', 'XO.'), ('X.O', 'OO.', 'XXX'), ('XXX', 'O.O', '...'), ('.OX', 'OXX', 'X.O'), ('OX.', 'XO.', 'X.O'), ('XXO', 'XXO', 'OOX'), ('.XO', 'OXO', 'XX.'), ('XXX', '.OO', 'OX.'), ('XX.', 'X.O', 'XOO'), ('..X', '.X.', 'XOO'), ('OXX', 'OOO', '.XX'), ('XXX', '...', '.OO'), ('XOO', 'OX.', 'X.X'), ('OOX', 'OX.', 'X.X'), ('XOO', 'XOO', 'XXX'), ('OOX', 'XOO', 'XXX'), ('XOO', 'OOX', 'XXX'), ('O.X', 'O.X', '..X'), ('O..', 'OXX', 'OX.'), ('OOX', 'OOX', 'XXX'), ('XOX', 'X..', 'XOO'), ('.O.', '..O', 'XXX'), ('O.X', 'XOX', 'O.X'), ('.XO', 'XXX', '.OO'), ('XXO', 'X.O', '..O'), ('O.X', '..X', 'O.X'), ('O..', 'XXX', 'OXO'), ('OOO', 'XX.', 'XOX'), ('XX.', 'OOO', '..X'), ('.XX', 'X..', 'OOO'), ('OX.', '.OX', 'X.O'), ('OXX', '.XO', 'X.O'), ('XXX', 'O.O', 'XO.'), ('X.O', 'XO.', 'OX.'), ('..O', '.OX', 'OXX'), ('X.X', 'OOX', '.OX'), ('OXO', 'XOO', 'XXX'), ('OXO', 'OOX', 'XXX'), ('O.O', '.OX', 'XXX'), ('O.O', 'XXO', 'XXO'), ('XXO', '.OO', 'XXO'), ('OXX', 'OOX', '.XO'), ('OXX', 'XOO', '.XO'), ('O.X', 'OOX', '.XX'), ('XXX', '.OO', '.XO'), ('XO.', 'X.X', 'XOO'), ('.OX', 'OO.', 'XXX'), ('XXO', 'XOX', 'O.O'), ('OXO', 'XX.', 'OX.'), ('.OX', 'O.O', 'XXX'), ('.XX', 'OXO', 'X.O'), ('.OX', 'XX.', 'XOO'), ('O.X', 'O.X', 'OX.'), ('O..', 'XXX', '.O.'), ('O..', 'XOX', '.XO'), ('X.X', 'OXO', 'O.X'), ('X.O', 'OXX', 'O.X'), ('XOO', 'X.O', 'X.X'), ('OXO', 'XX.', '.XO'), ('XOX', 'OXO', 'OXX'), ('OOX', '..X', '..X'), ('XOX', 'XOO', 'XXO'), ('OOO', '.X.', 'X.X'), ('XOX', 'OOX', 'XXO'), ('XXO', 'XO.', 'O..'), ('OOO', '.XX', 'OXX'), ('OXX', '.OX', 'O.X'), ('XXO', '.XO', 'OX.'), ('XXO', '.X.', 'OOX'), ('.OO', 'XXO', 'XXO'), ('OOO', '..X', 'X.X'), ('X..', 'XO.', 'XO.'), ('.OX', 'O.X', 'OXX'), ('O.X', 'XOO', 'XXO'), ('O.X', 'OOX', 'XXO'), ('XXX', 'OO.', 'X.O'), ('O.X', 'XO.', '.XO'), ('OO.', 'O.X', 'XXX'), ('X.O', 'XO.', 'XOX'), ('XXO', 'OOO', '.XX'), ('.XO', '.XO', '.X.'), ('X.X', 'OOO', 'OXX'), ('...', 'XXX', '.OO'), ('.O.', 'XXX', '..O'), ('OXX', 'O.X', 'O..'), ('.X.', 'OOO', '.XX'), ('O.X', 'OX.', 'XXO'), ('XOX', '.O.', 'XO.'), ('O.X', 'XOX', 'XOO'), ('O..', 'OXO', 'XXX'), ('X.O', 'XXO', 'XO.'), ('O.X', 'O.O', 'XXX'), ('X.O', 'X.O', 'X..'), ('.OX', '..X', '.OX'), ('XXX', 'OO.', 'O.X'), ('.O.', '.OX', 'XOX'), ('X.O', 'OX.', '..X'), ('XOX', '.XO', 'XO.'), ('O.X', 'OXX', 'XO.'), ('OO.', 'XXX', 'XO.'), ('XO.', 'XXX', 'OO.'), ('.OX', '.XO', 'XXO'), ('OO.', 'XOX', 'XOX'), ('OOO', 'XXO', 'X.X'), ('X.O', 'XOO', 'XX.'), ('XO.', 'X.O', 'XOX'), ('XXO', '.OX', 'OOX'), ('XO.', '.XO', 'OXX'), ('OOX', 'XOX', 'OXX'), ('XOX', 'OO.', 'XOX'), ('..X', 'OOO', '.XX'), ('OX.', '.X.', '.XO'), ('XO.', 'OOX', 'XOX'), ('..X', 'OX.', 'XO.'), ('OXX', 'X.X', 'OOO'), ('OX.', 'OXX', 'O..'), ('XOX', 'OX.', 'O.X'), ('OXO', 'OXX', 'O.X'), ('OXX', '.XO', '.XO'), ('XOO', '.XO', '.XX'), ('X.X', 'OXX', 'OOO'), ('XOX', 'O.X', '.OX'), ('OOO', 'X.X', 'X..'), ('.OO', 'X.O', 'XXX'), ('X.X', 'OOX', 'O.X'), ('OXO', 'XOX', 'XOX'), ('..O', 'XXX', 'OXO'), ('OXO', 'XOX', '.XO'), ('X.X', 'OX.', 'OOX'), ('OXX', 'OXO', 'XOX'), ('..X', 'OOX', 'XOX'), ('OXO', '.XO', '.XX'), ('XOO', 'XO.', 'X.X'), ('..O', 'X.O', 'XXO'), ('X.X', 'OX.', 'XOO'), ('XOO', 'XX.', 'X.O'), ('OOX', 'XX.', 'X.O'), ('X.O', 'XOO', 'X.X'), ('XX.', 'OXX', 'OOO'), ('O.O', 'XXX', 'X.O'), ('XOO', '.OX', 'OXX'), ('.OX', '.XO', 'XOX'), ('OOO', 'XX.', '.X.'), ('OXO', 'XOX', 'O.X'), ('XO.', 'XXX', 'O.O'), ('OXO', 'XO.', 'OXX'), ('XX.', '.XO', 'OOX'), ('XO.', 'OO.', 'XXX'), ('X.X', 'OXO', '.OX'), ('OXO', 'OXO', 'XXX'), ('XOO', 'XXO', '..X'), ('XXX', 'O..', 'O..'), ('..X', 'XX.', 'OOO'), ('O..', 'OX.', 'OXX'), ('OXX', '.XO', 'OX.'), ('.O.', 'XXX', '.O.'), ('OXO', '.OX', 'OXX'), ('.XO', 'XOX', 'OOX'), ('OXO', '.O.', 'XXX'), ('XO.', '.O.', 'XOX'), ('OOO', 'X..', '.XX'), ('..X', 'O.X', '.OX'), ('..X', '.OX', 'O.X'), ('OX.', '.X.', 'OX.'), ('XOO', 'XX.', 'XO.'), ('OOX', 'XX.', 'XO.'), ('OOO', '..X', 'XX.'), ('XXX', 'X.O', 'O.O'), ('.XX', 'OOX', '.OX'), ('OXX', 'OXO', 'XXO'), ('O.O', 'XXX', 'XO.'), ('XOX', 'OXO', 'XXO'), ('XXO', 'OX.', '.XO'), ('XX.', 'OOO', 'X..'), ('X.X', 'OXO', 'X.O'), ('.X.', 'OXO', 'XXO'), ('OXO', '.XX', '.XO'), ('OXO', 'XOX', 'OX.'), ('XXO', 'OXX', 'OOX'), ('XXO', 'OXX', 'XOO'), ('X.O', 'XXO', '.OX'), ('O.X', '.OX', 'X.O'), ('O.X', 'XOX', 'OXO'), ('..X', 'X.X', 'OOO'), ('OXO', 'O..', 'XXX'), ('X.O', 'XOX', 'OOX'), ('XOX', '.XX', 'OOO'), ('XOX', 'OXO', 'XOX'), ('X..', 'XOO', 'X..'), ('XXO', 'OX.', 'OX.'), ('OX.', 'XXX', 'OO.'), ('.OX', 'X.X', 'OOX'), ('.OX', 'OOX', 'X.X'), ('XXX', 'OOX', 'OXO'), ('XXO', '.OX', 'OXO'), ('XXX', 'XOO', 'OXO'), ('XXO', '.XO', '.OX'), ('.XO', 'XO.', 'O.X'), ('..X', 'OX.', 'X.O'), ('XOO', 'XXX', 'OOX'), ('OOX', 'XXX', 'OOX'), ('XOO', 'XXX', 'XOO'), ('OOX', 'XXX', 'XOO'), ('OXX', 'O.X', '.OX'), ('X..', 'OXO', '..X'), ('OOX', '.OX', '.XX'), ('OO.', 'XXX', '.OX'), ('.XX', 'XXO', 'OOO'), ('XOO', '.O.', 'XXX'), ('OOX', '.O.', 'XXX'), ('OX.', '.O.', 'XXO'), ('X..', 'OOO', '.XX'), ('XXX', 'XO.', '.OO'), ('.XO', 'XXX', 'O.O'), ('X.O', '.XO', 'XOX'), ('XO.', 'XOX', '.O.'), ('.OX', 'O.X', 'XOX'), ('.XX', 'OOO', 'OXX'), ('.O.', 'XOO', 'XXX'), ('O.X', 'XOX', '.OX'), ('.O.', 'OOX', 'XXX'), ('XOO', 'XOX', 'XXO'), ('OXX', 'XOX', '.OO'), ('O.O', 'O.X', 'XXX'), ('OO.', 'XXX', 'X.O'), ('OX.', 'XOX', 'OXO'), ('OOX', 'XOX', 'XO.'), ('X..', 'OOO', 'XX.'), ('..X', 'XXO', 'XOO'), ('OXX', '.OX', 'XOO'), ('XO.', 'XOO', 'X.X'), ('.XO', 'OX.', '.X.'), ('O.X', 'XXX', 'O.O'), ('O..', 'O.X', 'OXX'), ('XO.', '.OX', '.OX'), ('OO.', 'OX.', 'XXX'), ('XOX', '.XO', 'X.O'), ('OX.', 'XOO', 'XXO'), ('.OO', 'XXX', 'O.X'), ('OXX', 'OOX', '..X'), ('..X', 'OXX', 'OOX'), ('.OO', 'O.X', 'XXX'), ('OX.', 'OOX', 'XXO'), ('OOX', 'XO.', 'XXO'), ('OXO', '.XX', 'OX.'), ('..X', 'OXX', 'XOO'), ('OOX', 'X.X', 'O.X'), ('X.O', 'OXO', '.XX'), ('XXO', '.O.', 'O.X'), ('O..', '..O', 'XXX'), ('..X', '.OX', '.OX'), ('..X', 'O.X', 'O.X'), ('..O', 'XXX', 'O..'), ('.XO', 'OX.', 'XXO'), ('XX.', 'XXO', 'OOO'), ('OOX', 'XO.', 'XOX'), ('.XX', 'OOX', 'O.X'), ('XXX', 'OXO', '.O.'), ('OXO', 'XXO', '.X.'), ('.XX', 'OX.', 'XOO'), ('.XX', '.X.', 'OOO'), ('XOO', 'OXX', 'OXX'), ('OXO', 'XXX', 'OXO'), ('OXX', '.X.', 'OXO'), ('O..', 'O..', 'XXX'), ('XOX', 'OXX', 'XOO'), ('X..', 'X.O', 'XO.'), ('XOX', 'OXX', 'OOX'), ('.XO', '.X.', '.XO'), ('OXX', 'XOO', 'XOX'), ('OXX', 'OOX', 'XOX'), ('XOO', '.XX', '.OX'), ('OOX', '.XX', '.OX'), ('OX.', '.XO', '.X.'), ('..X', 'OXO', 'XOX'), ('XOO', '.OX', 'XOX'), ('XOX', '.X.', 'OOX'), ('XOX', '.X.', 'XOO'), ('X.X', 'XOO', 'X.O'), ('..O', 'XXX', '..O'), ('O.X', '.X.', 'XO.'), ('.OX', 'OXX', '.OX'), ('.XX', 'OOO', '..X'), ('XO.', 'XO.', 'XXO'), ('.OX', '.O.', 'XOX'), ('XOO', 'X.O', 'XX.'), ('.OO', 'XOX', 'OXX'), ('XXX', 'O..', 'OXO'), ('XO.', 'XXO', '.OX'), ('XXX', 'X.O', '.OO'), ('.OX', 'XXO', 'XO.'), ('OXX', '.XO', 'XO.'), ('OXO', 'XO.', 'XXO'), ('XO.', 'OXO', 'X.X'), ('.O.', 'XXX', 'O..'), ('X.O', 'X.O', '.XO'), ('XO.', 'OXX', 'O.X'), ('XXX', 'OO.', '.OX'), ('.OX', '..X', 'O.X'), ('XOX', 'X.O', 'X.O'), ('OOO', 'X.X', '..X'), ('XO.', 'XXO', 'XO.'), ('XOO', 'X..', 'X..'), ('OXO', '.OX', 'XXO'), ('XXX', 'O..', '.O.'), ('..X', '.XX', 'OOO'), ('XXX', 'OX.', 'OO.'), ('XXX', 'O.X', '.OO'), ('.OX', 'OXX', 'XO.'), ('.XO', 'X.O', '.XO'), ('XX.', 'XOX', 'OOO'), ('.XO', '.X.', 'OX.'), ('OOX', '.XX', 'XO.'), ('OX.', '.XX', 'OXO'), ('XXO', 'XO.', 'XO.'), ('OOO', 'XOX', '.XX'), ('.XO', 'XOO', 'OXX'), ('.XO', 'OOX', 'OXX'), ('.OX', '.XX', 'OOX'), ('OXX', 'OOX', 'OX.'), ('XXO', '.O.', 'OX.'), ('.OX', '.XX', 'XOO'), ('X.O', '.X.', 'O.X'), ('OXX', 'XO.', 'XOO'), ('.OO', 'XXX', 'XO.'), ('OX.', 'OOX', 'OXX'), ('OXO', 'XXO', 'X.O'), ('O..', 'XXX', '..O'), ('X..', 'XOO', 'XXO'), ('XOX', 'XOX', 'OO.'), ('OOX', 'XXO', 'XXO'), ('OXX', 'OX.', 'OOX'), ('.OX', '.X.', 'XO.'), ('OX.', 'OX.', 'XXO'), ('XXX', 'OOX', 'O..'), ('.OX', 'OXO', 'X.X'), ('XXX', 'OXO', 'OXO'), ('X.O', '.XO', 'OXX'), ('.OO', '.OX', 'XXX'), ('O.X', 'XXX', 'OO.'), ('OXX', 'XXO', 'OOX'), ('OXX', 'XXO', 'XOO'), ('X.X', 'XXO', 'OOO'), ('XXX', 'XOO', 'O..'), ('X..', 'XOO', 'XOX'), ('.XX', 'OOO', 'XOX'), ('.X.', 'OOO', 'XX.'), ('.X.', 'OXX', 'OXO'), ('OX.', 'O.X', 'OX.'), ('..O', 'XOX', 'OX.'), ('..X', '.XO', 'X.O'), ('OXO', 'XXX', 'OOX'), ('XXO', 'OOO', 'XX.'), ('.X.', 'OXO', 'OXX'), ('OXO', 'XXX', 'XOO'), ('OXX', '.X.', 'XOO'), ('XX.', 'OX.', 'OOX'), ('OXO', 'XXX', '.O.'), ('O.X', 'OXX', 'O..'), ('OXX', 'OO.', 'XXO'), ('XOX', 'OXX', 'OXO'), ('OOO', '.X.', 'XX.'), ('XXO', 'OXO', '..X'), ('XOO', 'O..', 'XXX'), ('OOX', 'O..', 'XXX'), ('.X.', 'X.X', 'OOO'), ('.XX', 'OX.', 'OXO'), ('OO.', 'XO.', 'XXX'), ('OOO', 'XOX', 'XX.'), ('.OO', 'XXX', '...'), ('.OX', 'XOX', 'O.X'), ('.XO', '.XX', 'OXO'), ('.OX', 'XO.', 'XO.'), ('OXX', '.OX', 'OXO'), ('..O', 'XOO', 'XXX'), ('..O', 'OOX', 'XXX'), ('XOX', 'O.X', 'O.X'), ('X.O', 'XX.', 'OOX'), ('X.O', 'XX.', 'XOO'), ('O.O', 'X.O', 'XXX'), ('O..', '.O.', 'XXX'), ('O.X', 'OXO', 'XX.'), ('OXX', 'O.O', 'OXX'), ('XOO', 'X..', 'XXO'), ('XOX', 'OOO', 'X.X'), ('XO.', '.OX', 'XO.'), ('XOO', 'X.X', 'X.O'), ('.XX', '..X', 'OOO'), ('O.O', 'XOX', 'XXO'), ('O.X', 'XXO', 'X.O'), ('X..', '.X.', 'OOX'), ('O.O', 'XXX', '...'), ('XX.', 'OOO', 'OXX'), ('X.O', '.OX', 'OX.'), ('OXX', 'OOO', 'X.X'), ('OXX', 'XO.', '..O'), ('XOO', 'OX.', '.XX'), ('OX.', 'XXO', '.XO'), ('O..', 'XXX', 'O..'), ('.OX', 'OXX', 'O.X'), ('XXO', '..O', 'X.O'), ('XXX', 'OX.', 'O.O'), ('XO.', 'XXO', 'O.X'), ('O.X', 'OO.', 'XXX'), ('X.O', 'XXO', '..O'), ('OXX', 'XOO', 'OXX'), ('XOX', 'XX.', 'OOO'), ('.OX', '.OX', '..X'), ('XXX', 'O.O', 'OX.'), ('X.O', '.X.', '.OX'), ('XXO', 'XOO', '.XO'), ('X.X', 'X..', 'OOO'), ('XO.', 'OXX', '.OX'), ('OX.', 'XX.', 'OXO'), ('XXO', 'XXO', 'O.O'), ('O.O', 'XXX', '.OX'), ('OX.', '.XO', 'XXO'), ('O.X', 'X.X', 'OOX'), ('.OO', '...', 'XXX'), ('OOO', '.XX', '..X'), ('XXX', 'O.X', 'O.O'), ('XOO', 'XX.', '.OX'), ('.XX', 'OXO', '.XO'), ('O..', 'XOO', 'XXX'), ('O..', 'OOX', 'XXX'), ('OXX', 'OO.', 'OXX'), ('O..', 'XO.', 'XXO'), ('.OX', '.XO', 'X..'), ('X.O', '.OX', 'O.X'), ('XXX', '.OO', 'X.O'), ('OOO', 'OXX', 'X.X'), ('XO.', '.XO', '..X'), ('XOO', 'X.X', 'XO.'), ('XXO', 'OXX', 'OXO'), ('XXO', '.XX', 'OOO'), ('O.X', 'XXX', '.OO'), ('OX.', '.OX', '.XO'), ('XX.', '.X.', 'OOO'), ('O.X', '.OX', 'OXX'), ('OOO', '.X.', '.XX'), ('..O', '.XO', 'XXO'), ('XO.', 'X..', 'XO.'), ('X.O', 'OX.', 'OXX'), ('OXX', '.O.', 'X.O'), ('.X.', 'OXO', '.X.'), ('XXX', 'OXO', 'O..'), ('XOO', 'XOX', 'X..'), ('XOO', '.X.', '..X'), ('.XO', 'XOX', 'OXO'), ('OOO', '.XX', 'XOX'), ('OX.', 'OXX', '.XO'), ('XX.', 'OOO', '.X.'), ('.OO', 'XXX', '.OX'), ('XXX', 'O..', '..O'), ('OX.', '.OO', 'XXX'), ('XOX', 'XOO', '.OX'), ('X.X', 'OOO', 'XOX'), ('OXO', 'OXX', '.X.'), ('XXO', 'OOO', 'X.X'), ('XXO', '.OO', 'OXX'), ('XOO', 'XOX', 'OX.'), ('.OX', '.OX', 'OXX'), ('XX.', 'XO.', 'XOO'), ('OXX', 'XOX', 'O.O'), ('XXX', 'O.X', 'OO.'), ('X.O', '.XX', 'OOX'), ('XX.', 'OOO', 'XXO'), ('X.X', '.OX', 'OOX'), ('.X.', 'OOO', 'X.X'), ('XXX', 'OO.', 'OX.'), ('OX.', 'O.O', 'XXX'), ('XXX', '..O', 'O..'), ('O.X', 'OX.', 'O.X'), ('OXX', 'OX.', 'X.O'), ('OOX', 'OXX', 'X..'), ('..O', 'XXX', '.O.'), ('..O', 'XXX', 'OOX'), ('..O', 'XXX', 'XOO'), ('.OO', 'XXX', '.XO'), ('OOX', '..X', 'OXX'), ('XOX', 'OXO', '..X'), ('XOX', 'OOO', 'XX.'), ('XXO', 'XO.', 'X.O'), ('X.O', 'XO.', 'X..'), ('OOO', 'XX.', 'X..'), ('.XO', 'XOO', 'XXO'), ('XXX', '.O.', 'O..'), ('OOO', '.XX', 'XXO'), ('OXX', '.XX', 'OOO'), ('XO.', '.XO', 'XOX'), ('X.O', 'XOX', 'XO.'), ('XOO', 'XXO', 'OXX'), ('OOX', 'XXO', 'OXX'), ('..X', '.XO', 'XO.'), ('X.X', 'OOO', 'X..'), ('XOO', '.XO', 'X.X'), ('OOX', '.XO', 'X.X'), ('XOX', 'OXO', 'X..'), ('.OX', '.X.', 'X.O'), ('XOX', 'OX.', 'X.O'), ('OO.', 'XXX', '.XO'), ('XX.', 'OXO', 'OX.'), ('XOX', 'OOX', '..X'), ('OOO', '.XX', 'X..'), ('OXX', 'OX.', '.XO'), ('.XO', 'XXO', 'OX.'), ('XOO', 'OXX', '..X'), ('OOX', 'OXX', '..X'), ('XX.', 'OOO', 'XOX'), ('O.X', 'OXX', '.OX'), ('.XX', '.XO', 'OXO'), ('OOO', '.XX', '.X.'), ('XOX', 'XO.', '.O.'), ('XXX', 'OO.', '...'), ('OOO', 'X..', 'XX.'), ('OX.', 'OX.', 'O.X'), ('..O', 'XO.', 'OXX'), ('XOX', '.O.', '.OX'), ('OX.', 'XOX', '..O'), ('XXX', '.OX', '.OO'), ('O.O', 'XXX', '.XO'), ('.XO', '.OX', 'O.X'), ('OOX', 'OXO', 'XXX'), ('XOO', 'OXO', 'XXX'), ('.XX', '.XO', 'XOO'), ('O.X', '.X.', 'X.O'), ('OXX', '..X', 'OOX'), ('O.X', 'OX.', 'X..'), ('X.O', '.OO', 'XXX'), ('OX.', '.XO', 'OXX'), ('XXO', 'OX.', '.OX'), ('X.O', 'X.O', 'XOX'), ('XOX', '.OX', 'XOO'), ('OXO', 'XOX', 'X.O'), ('OXX', '.O.', '.XO'), ('OOX', 'XOX', '..X'), ('X.O', 'XO.', 'O.X'), ('O.O', 'XXX', 'O.X'), ('O.X', 'O..', 'OXX'), ('XOX', '.OX', 'O.X'), ('X.O', 'XO.', 'XXO'), ('OXX', 'XXO', 'OXO'), ('X..', 'XX.', 'OOO'), ('.X.', '.X.', 'OXO'), ('O.O', 'XXX', 'OX.'), ('XOO', 'XX.', 'O.X'), ('XO.', '.OO', 'XXX'), ('.X.', 'XXO', 'OXO'), ('O.X', 'OX.', 'XOX'), ('XOX', 'XOX', '.OO'), ('O.X', '.XX', 'OOX'), ('O.X', '.XX', 'XOO'), ('XO.', 'OX.', 'XOX'), ('OOX', 'O.X', 'X.X'), ('.XO', 'XXO', '..O'), ('.XO', '.OX', 'OX.'), ('.OX', 'XXO', 'X.O'), ('OO.', 'XOX', 'XXO'), ('XX.', 'OXO', '.XO'), ('XXX', '.XO', 'O.O'), ('XXO', '.OX', 'O..'), ('XOX', 'X.X', 'OOO'), ('X.O', '..O', 'XXO'), ('.OX', 'OOX', '.XX'), ('X.X', 'XOO', 'XO.'), ('XX.', 'OXO', 'O.X'), ('X..', 'X.O', 'X.O'), ('OOX', '.OX', 'X.X'), ('XOO', 'XXX', 'OXO'), ('OOX', 'XXX', 'OXO'), ('OO.', '.OX', 'XXX'), ('O.X', '.OX', 'XOX'), ('.OO', 'XXX', 'OX.'), ('..O', 'OXO', 'XXX'), ('XOX', 'XXO', 'OOX'), ('OO.', '...', 'XXX'), ('OXO', '.X.', 'XXO'), ('OOX', 'XOX', 'X.O'), ('XXO', 'OXO', 'XOX'), ('XOX', 'XXO', 'XOO'), ('X..', 'OXX', 'OOX'), ('XXX', 'X.O', 'OO.'), ('XXO', 'X.O', 'XO.'), ('X..', 'OOO', 'X.X'), ('.XO', 'XOX', 'O..'), ('XXX', 'OX.', '.OO'), ('X..', '.XX', 'OOO'), ('.XX', '.OX', 'OOX'), ('XOX', '..X', 'OOX'), ('X..', 'XXO', 'OOX'), ('X..', 'XXO', 'XOO'), ('O.O', 'OX.', 'XXX'), ('XO.', 'OX.', '..X'), ('OXO', 'OX.', '.XX'), ('X.O', '.XO', '.XO'), ('O.X', '.XO', 'X..'), ('O.X', '.OX', '..X'), ('XXO', 'XOO', 'X..'), ('XOO', 'XOX', 'O.X'), ('X..', 'OXO', 'XOX'), ('..O', '..O', 'XXX'), ('OXX', 'OX.', 'O..'), ('O.O', 'XO.', 'XXX'), ('.XO', 'X.O', 'X.O'), ('OXX', 'OOX', 'X.O'), ('OXX', 'XOO', 'X.O'), ('X.O', 'XOX', 'OXO'), ('XOX', 'XO.', 'X.O'), ('.O.', 'XOX', '.OX'), ('XOO', '.XX', 'O.X'), ('OOX', '.XX', 'O.X'), ('XXX', '.O.', 'OXO'), ('.XX', 'OOO', 'X..'), ('X.X', 'OXO', 'XO.'), ('OXX', 'XOX', 'OOX'), ('...', '.OO', 'XXX'), ('XXX', 'OXO', '..O'), ('.XX', 'OOO', '.X.'), ('XO.', '.X.', '.OX'), ('.X.', '.XO', '.XO'), ('XXO', 'XOX', 'OO.'), ('X..', '.XO', '.OX'), ('X.O', 'O.O', 'XXX'), ('OOO', 'X.X', '.X.'), ('OO.', 'XXX', '...'), ('X.X', '.X.', 'OOO'), ('XXO', '.XO', '..O'), ('.OO', 'OX.', 'XXX'), ('XXX', 'OO.', '.XO'), ('X.X', 'XO.', 'XOO'), ('XXX', '.XO', 'OO.'), ('.OX', 'XOO', 'XOX'), ('.OX', '.OO', 'XXX'), ('XOO', 'OXX', 'XOX'), ('OOX', 'OXX', 'XOX'), ('OOX', 'XOX', '.XO'), ('XXO', 'OOX', 'OX.'), ('XXO', 'XOO', 'OX.'), ('.XX', 'XOX', 'OOO'), ('.X.', 'XX.', 'OOO'), ('OXX', '.OX', '..O'), ('OXO', '.X.', 'OXX'), ('OXX', 'OXX', 'XOO'), ('XO.', 'X.O', 'XXO'), ('X.X', 'X.O', 'XOO'), ('.O.', 'XXX', 'OOX'), ('XO.', 'OX.', 'OXX'), ('.O.', 'O..', 'XXX'), ('.O.', 'XXX', 'XOO'), ('XO.', '.XX', 'OOX'), ('X..', 'OX.', '.OX'), ('OX.', 'OX.', '.X.'), ('O.X', 'OOX', 'X.X'), ('OX.', 'OO.', 'XXX'), ('XXX', '..O', '..O'), ('OOO', 'XX.', '..X'), ('.XO', 'OXX', 'OX.'), ('XO.', 'XOO', 'XX.'), ('O.X', '..X', '.OX'), ('XOX', '.OO', 'XOX'), ('OXO', 'OXX', 'XXO'), ('XOO', 'OXX', 'XXO'), ('OOX', 'OXX', 'XXO'), ('X.X', 'O.X', 'OOX'), ('XXX', 'XO.', 'OO.'), ('OOX', 'OX.', 'XX.'), ('.XO', 'OXX', '.XO'), ('O.X', '.OO', 'XXX'), ('..O', 'XXO', '.XO'), ('OOX', 'OXX', 'OX.'), ('XXO', 'XO.', 'OXO'), ('XXX', 'OXO', 'OOX'), ('XXX', 'OXO', 'XOO'), ('OOO', 'X.X', 'OXX'), ('XOO', 'XO.', 'XX.'), ('XOO', 'XXX', 'O..'), ('OOX', 'XXX', 'O..'), ('XXO', 'OXO', 'OXX'), ('OO.', 'X.O', 'XXX'), ('XOX', 'XXO', 'OXO'), ('XX.', '..X', 'OOO'), ('OOO', '..X', '.XX'), ('XXO', 'X.O', 'OXO'), ('.XO', 'XX.', 'OXO'), ('OX.', 'XXX', '.OO'), ('XOX', 'XOO', 'OXX'), ('XOX', 'OOX', 'OXX'), ('XXX', '..O', '.O.'), ('OXO', 'OXX', 'XOX'), ('X..', 'X.X', 'OOO'), ('.OX', 'OX.', 'X..'), ('XO.', 'XOX', 'OOX'), ('X.O', 'XXO', 'OXO'), ('X.O', '.O.', 'OXX')}
	while True:
		s = input()
		if s == 'end':
			break
		print('valid' if tuple([s[:3], s[3:6], s[6:9]]) in his else 'invalid')
import collections

def kingpath():

	def adds(x, y, c):
		s = (x, y)
		if s in sgs and s not in his:
			todo.append([x, y, c + 1])
			his.add(s)
	(startx, starty, endx, endy) = map(int, input().split())
	seg = int(input())
	sgs = set()
	for i in range(seg):
		(row, s, e) = map(int, input().split())
		for i1 in range(s, e + 1):
			sgs.add((row, i1))
	todo = collections.deque([[startx, starty, 0]])
	his = set()
	while todo:
		(x, y, step) = todo.popleft()
		if x == endx and y == endy:
			return step
		adds(x - 1, y, step)
		adds(x + 1, y, step)
		adds(x, y - 1, step)
		adds(x, y + 1, step)
		adds(x - 1, y - 1, step)
		adds(x + 1, y + 1, step)
		adds(x - 1, y + 1, step)
		adds(x + 1, y - 1, step)
	return -1

def postin():
	buildings = int(input())
	l = []
	c = 0
	for _ in range(buildings):
		(d, h) = map(int, input().split())
		while l and l[-1] > h:
			l.pop()
		if l and l[-1] != h or not l:
			c += 1
			l.append(h)
	return c
import collections

def q1():
	for _ in range(int(input())):
		num = int(input())
		c = sorted(list(collections.Counter(input().split()).items()), key=lambda x: int(x[0]))
		ans = []
		for i in range(len(c)):
			ans.append(c[i][0])
			c[i] = [c[i][0]] + [c[i][1] - 1]
		for i in c:
			if i[1]:
				ans += i[1] * [i[0]]
		print(*ans, sep=' ')

def q2():
	for _ in range(int(input())):
		(num, m) = map(int, input().split())
		(now, *l) = input().split()
		c = 1
		num -= 1
		while l:
			now = int(now)
			for i in range(num):
				if not (now + int(l[i])) % m:
					now = l.pop(i)
					break
			else:
				c += 1
				(now, *l) = l
			num -= 1
		print(c)

def q2re():
	for _ in range(int(input())):
		counter = collections.defaultdict(int)
		(num, m) = map(int, input().split())
		ans = 0
		for i in input().split():
			counter[int(i) % m] += 1
		if counter[0]:
			ans += 1
		his = set()
		for i in list(counter.keys()):
			if i and i not in his:
				his.add(m - i)
				ans += 1
				ans += max(0, abs(counter[i] - counter[m - i]) - 1)
		print(ans)

def c1(num):
	if num % 2:
		return [1, num // 2, num // 2]
	else:
		half = num // 2
		if half % 2:
			return [2, half - 1, half - 1]
		else:
			return [half // 2, half // 2, half]

def c1call():
	for _ in range(int(input())):
		print(*c1(int(input().split()[0])), sep=' ')

def c2call():
	for _ in range(int(input())):
		(num, k) = map(int, input().split())
		print(*[1] * (k - 3), *c1(num - (k - 3)), sep=' ')

def dominos():
	for _ in range(int(input())):
		(n, k, k1) = map(int, input().split())
		(w, b) = map(int, input().split())
		if k1 > k:
			r = k1 - k
			w -= k
			w -= r // 2
			br = n - k - (n - k1)
			b -= n - k1
			b -= br // 2
		elif k1 < k:
			r = k - k1
			w -= k1
			w -= r // 2
			br = n - k1 - (n - k)
			b -= n - k
			b -= br // 2
		else:
			w -= k1
			b -= n - k
		print('yes' if b <= 0 and w <= 0 else 'no')

def biremove():
	for _ in range(int(input())):
		s = input()
		if ''.join(sorted(s)) == s:
			print('yes')
		else:
			for i in range(len(s) - 1):
				if s[i] == '1' and s[i + 1] == '1':
					pos = i
					break
			else:
				print('yes')
				continue
			for i in range(pos + 1, len(s) - 1):
				if s[i] == '0' and s[i + 1] == '0':
					break
			else:
				print('yes')
				continue
			print('no')
biremove()


import sys
from math import *
from collections import defaultdict, Counter
t = int(input())
for i in range(t):
	s = input()
	no = s.count('0')
	ed = s.count('1')
	if no == len(s) or ed == len(s):
		print('YES')
		continue
	po1 = 1000000000.0
	for i in range(1, len(s)):
		if s[i] == '1' and s[i - 1] == '1':
			po1 = i
			break
	po0 = -1
	for i in range(len(s) - 1, 0, -1):
		if s[i] == '0' and s[i - 1] == '0':
			po0 = i
			break
	if po1 < po0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	a = s.find('11')
	b = s.rfind('00')
	if a != -1 and b != -1 and (a < b):
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	s = input()
	i1 = s.find('11')
	i2 = s.rfind('00')
	if i1 != -1 and i2 != -1 and (i1 < i2):
		print('NO')
	else:
		print('YES')


t = int(input())
results = []

def find_dob(s):
	return [(i, s[i]) for i in range(len(s) - 1) if not s[i] ^ s[i + 1]]
for i in range(t):
	s = input()
	s = [int(c) for c in s]
	dobs = find_dob(s)
	dobs_z = [a for (a, b) in dobs if b == 0]
	dobs_o = [a for (a, b) in dobs if b == 1]
	if len(dobs_z) == 0 or len(dobs_o) == 0:
		results.append('yes')
	elif dobs_z[-1] < dobs_o[0]:
		results.append('yes')
	else:
		results.append('no')
for i in range(t):
	print(results.pop(0))


def increasing(arr):
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			return False
	return True
t = int(input())
for i in range(t):
	s = input()
	index1 = s.find('11')
	index0 = s.find('00', index1)
	if index1 != -1:
		if index0 > index1:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for i in range(int(input())):
	a = input()
	x = a.find('11')
	if a[x:].find('00') != -1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	n = len(s)
	f = True
	(o, z) = (s.count('1'), s.count('0'))
	if o == n or z == n:
		print('YES')
		continue
	for i in range(n - 1):
		if s[i] == '1' and s[i + 1] == '1':
			for i in range(i + 2, n - 1):
				if s[i] == '0' and s[i + 1] == '0':
					f = False
	if f:
		print('YES')
	else:
		print('NO')


for _ in ' ' * int(input()):
	s = input()
	print('YNEOS'[s.find('00', s.find('11')) != -1::2])


import bisect
for _ in range(int(input())):
	prev = -10
	a = input()
	p = True
	if '11' in a and '00' in a:
		if len(a) - 1 - a[::-1].index('00') - 1 > a.index('11'):
			p = False
	print('NO' if p == False else 'YES')


n = int(input())
for i in range(n):
	x = str(input())
	a = x.find('11')
	b = x.rfind('00')
	if a != -1 and b != -1 and (a < b):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	n = len(s)
	t = s[::-1]
	idx11 = s.find('11')
	x = t.find('00')
	if x != -1:
		idx00 = n - t.find('00') - 1
	else:
		idx00 = x
	if idx00 != -1 and idx11 != -1 and (idx00 > idx11):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	milgaya_one = 0
	yahase_zero_dekh = -1
	for i in range(0, len(s) - 1):
		if s[i] == s[i + 1] and s[i] == '1':
			milgaya_one = 1
			yahase_zero_dekh = i + 2
			break
	if milgaya_one == 0:
		print('YES')
		continue
	milgaya_zero = 0
	for i in range(yahase_zero_dekh, len(s) - 1):
		if s[i] == s[i + 1] and s[i] == '0':
			milgaya_zero = 1
			break
	if milgaya_zero == 1:
		print('NO')
	else:
		print('YES')


from collections import Counter
for _ in range(int(input())):
	s = input()
	n = len(s)
	last0 = -1
	last1 = -1
	f = 0
	f2 = 0
	for i in range(n):
		if s[i] == '0' and f == 0:
			last0 = i
		elif s[i] == '1' and f == 0:
			if i != n - 1 and s[i + 1] == '1':
				f = 1
				continue
			else:
				continue
		elif s[i] == '0' and f == 1:
			if i != n - 1 and s[i + 1] == '0':
				f2 = 1
				break
			else:
				continue
	if f2 == 0:
		print('YES')
	else:
		print('NO')


testcase = input()
i = 1
while i <= int(testcase):
	str = input()
	x = 1
	while x < len(str):
		if str[x - 1] == str[x] and str[x] == '1' and (x < len(str) - 2):
			y = x + 2
			while y < len(str):
				if str[y - 1] == str[y] and str[y] == '0':
					print('No')
					break
				y = y + 1
			if y == len(str):
				print('Yes')
			break
		x = x + 1
	if x == len(str):
		print('Yes')
	i = i + 1


t = int(input())
for i in range(0, t):
	m = input()
	x = m.find('11')
	y = m.rfind('00')
	if x == -1 or y == -1:
		ans = 'YES'
	elif x < y:
		ans = 'NO'
	else:
		ans = 'YES'
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input().rstrip()
	zeros = []
	ones = []
	for i in range(len(s) - 1):
		if s[i] == s[i + 1] == '0':
			zeros.append(i)
		elif s[i] == s[i + 1] == '1':
			ones.append(i)
	if not zeros or not ones:
		print('YES')
	elif max(zeros) > min(ones):
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	l = input()
	n = len(l)
	flag = 0
	for i in range(n - 1):
		if flag == 0 and l[i] == '1' and (l[i + 1] == '1'):
			flag = 1
		if flag == 1 and l[i] == '0' and (l[i + 1] == '0'):
			flag = 2
	if flag == 2:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = str(input())
	ans = 'YES'
	for i in range(len(s) - 1):
		if s[i] == '1' and s[i + 1] == '1':
			for j in range(i + 2, len(s) - 1):
				if s[j] == '0' and s[j + 1] == '0':
					ans = 'NO'
					break
		if ans == 'NO':
			break
	print(ans)


import sys

def II():
	return int(sys.stdin.readline())

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

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

def SI():
	return sys.stdin.readline().strip()
t = II()
for s1 in range(t):
	s = SI()
	a = False
	b = False
	check = True
	for i in range(len(s) - 1):
		if s[i] == s[i + 1] and s[i] == '1':
			a = True
		elif s[i] == s[i + 1] and s[i] == '0':
			if a:
				check = False
				break
	if check:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	a = s.find('11')
	if '00' in s[a:]:
		print('NO')
	else:
		print('YES')


def check(s):
	n = len(s)
	i = 0
	while i < n - 1:
		if s[i] == '1' and s[i + 1] == '1':
			break
		i += 1
	while i < n - 1:
		if s[i] == '0' and s[i + 1] == '0':
			return False
		i += 1
	return True
t = int(input())
while t:
	s = input()
	if check(s):
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	s = input()
	ans = s.replace('10', '')
	print('YES' if ans == ''.join(sorted(ans)) else 'NO')


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

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

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[1]

def sort2(l):
	return sorted(l, key=getKey, reverse=True)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def ceil(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	for _ in range(ii()):
		s = si()
		n = len(s)
		l = []
		c = 1
		for i in range(1, n):
			if s[i] == s[i - 1]:
				c += 1
			else:
				l.append([c, int(s[i - 1])])
				c = 1
		l.append([c, int(s[-1])])
		if len(l) == 1:
			print('YES')
			continue
		m = len(l)
		flag = 1
		f = 1
		for i in range(m - 1, -1, -1):
			if l[i][0] > 1:
				if l[i][1] == 1:
					if f == 0:
						flag = 0
						break
					f = 1
				else:
					f = 0
		if flag:
			print('YES')
		else:
			print('NO')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for i in range(t):
	a = []
	b = input()
	e = 1
	w = 0
	while w <= len(b):
		if b[w:w + 2] == '00':
			a.append(0)
			w += 2
		elif b[w:w + 2] == '11':
			a.append(1)
			w += 2
		else:
			w += 1
	for i in range(len(a) - 1):
		if a[i] > a[i + 1]:
			e = -1
	if e == -1:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	s = input()
	idx = 0
	if not s.startswith('11'):
		idx = s.find('011')
		if idx == -1:
			print('YES')
			continue
	idx = s.find('100', idx)
	if idx == -1:
		print('YES')
		continue
	print('NO')


for _ in range(int(input())):
	s = input()
	ans = 'yes'
	i = s.rfind('00')
	s1 = s[0:i + 1]
	if i != -1 and s1.count('11') != 0:
		ans = 'no'
	print(ans)


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mp = lambda : map(int, input().split())
it = lambda : int(input())
ls = lambda : list(input().strip())
mt = lambda r: [ls() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def fibo_n(n):
	return ((1 + sqrt(5)) / 2) ** n / sqrt(5)
mod = 1000000007

def out(a, test, answer):
	if answer != 'IMPOSSIBLE':
		print('Case #{}: '.format(test + 1), end=' ')
		for el in range(1, a + 1):
			print(v[el], end=' ')
		print()
	else:
		print('Case #{}: {}'.format(test + 1, answer))

def LCS(a, b):
	n = len(a)
	m = len(b)
	t = [[0 for i in range(m + 1)] for j in range(n + 1)]
	mx = 0
	for fst in range(1, n + 1):
		for scd in range(1, m + 1):
			if a[fst - 1] == b[scd - 1]:
				t[fst][scd] = 1 + t[fst - 1][scd - 1]
			mx = max(mx, t[fst][scd])
	return n + m - 2 * mx
for _ in range(it()):
	a = input().strip()
	one = None
	zero = None
	for j in range(1, len(a)):
		if one == None and a[j] + a[j - 1] == '11':
			one = j
		if a[j] + a[j - 1] == '00':
			zero = j
	if one == None or zero == None:
		print('YES')
	elif one < zero:
		print('NO')
	else:
		print('YES')


list1 = []
for i in range(int(input())):
	s = input()
	if '00' in s and '11' not in s or ('11' in s and '00' not in s) or s.find('11') > s.rfind('00') or ('00' not in s and '11' not in s):
		list1.append('YES')
	else:
		list1.append('NO')
print(*list1, sep='\n')


from queue import Queue
from itertools import accumulate
from io import BytesIO, IOBase
from itertools import combinations
import threading
from collections import deque
from functools import reduce, cmp_to_key
import sys
from math import sqrt
import heapq
import random
import math
from collections import defaultdict
from collections import Counter
import io
import os
import bisect
from fractions import Fraction

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def swap(arr, a, b):
	(arr[a], arr[b]) = (arr[b], arr[a])
t = 1
t = iinput()
for _ in range(t):
	s = input()
	min1 = float('inf')
	max0 = -float('inf')
	for i in range(len(s) - 1):
		val = s[i] + s[i + 1]
		if val == '11':
			min1 = min(min1, i)
		if val == '00':
			max0 = max(max0, i)
	if min1 < max0:
		print('NO')
	else:
		print('YES')


for s in [*open(0)][1:]:
	print('YNEOS'['00' in s[s.find('11'):]::2])


for _ in range(int(input())):
	s = input()
	z = -2
	a = True
	for (i, el) in enumerate(s):
		if not a:
			break
		if el == '1':
			if z + 1 == i:
				if s[z:].count('00') == 0:
					a = True
				else:
					a = False
			else:
				z = i
	if a:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	k = s.find('11')
	if k != -1 and '00' in s[k:]:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(0, t):
	s = input()
	lst = list(s)
	n = 0
	c = False
	for j in range(0, len(lst) - 1):
		if lst[j] == '1' and lst[j + 1] == '1':
			n = j + 1
			c = True
			break
	if c:
		answer = True
		for k in range(n, len(lst) - 1):
			if lst[k] == '0' and lst[k + 1] == '0':
				print('NO')
				answer = False
				break
			else:
				answer = True
		if answer:
			print('YES')
	else:
		print('YES')


t = int(input())
while t:
	f = 0
	t = t - 1
	l = input()
	if '11' in l:
		s = l.index('11')
		if '00' in l[s + 1:]:
			print('NO')
			f = 1
			continue
	if f == 0:
		print('YES')


for i in range(int(input())):
	s = input()
	x = s.find('11')
	y = s.rfind('00')
	if x != -1 and x < y and (x != -1):
		print('NO')
	else:
		print('YES')


def solve(s):
	i = s.find('11')
	j = s.rfind('00')
	if i != -1 and j != -1 and (i < j):
		return 'NO'
	else:
		return 'YES'

def main():
	t = int(input())
	for i in range(t):
		print(solve(input()))
main()


for _ in range(int(input())):
	a = input()
	try:
		z = a.index('11')
	except:
		z = len(a)
	try:
		t = len(a) - a[::-1].index('00')
	except:
		t = 0
	if z < t:
		print('NO')
	else:
		print('YES')


def solve_problem(string):
	start = string.find('11')
	if start < 0:
		print('YES')
		return
	previousZero = False
	for i in range(start + 2, len(string)):
		if string[i] == '0':
			if previousZero:
				print('NO')
				return
			else:
				previousZero = True
		else:
			previousZero = False
	print('YES')

def solve():
	t = int(input())
	for i in range(0, t):
		string = input().strip()
		solve_problem(string)
solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input().strip()
	if s.find('11') < s.rfind('00') and s.find('11') != -1 and (s.rfind('00') != -1):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = list(input())
	ssort = sorted(s)
	if s == ssort:
		ans = 'YES'
	elif len(s) <= 3:
		ans = 'YES'
	else:
		remove1 = True
		ans = 'YES'
		for i in range(len(s) - 1):
			if remove1:
				if s[i] == '1' and s[i + 1] == '1':
					remove1 = False
			elif s[i] == '0' and s[i + 1] == '0':
				ans = 'NO'
				break
	print(ans)


import sys
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)
for i in range(int(input())):
	s = input()
	n = s.find('11')
	m = s.rfind('00')
	if n < m and n != -1 and (m != -1):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input().strip()
	one = s.find('11')
	l = s[one:].find('00')
	print('YES' if l < 0 else 'NO')


for st in range(int(input())):
	now = input()
	f = now.find('11')
	if f == -1:
		print('YES')
		continue
	ind = -1
	for i in range(len(now), -1, -1):
		if now[i:i + 2] == '00':
			ind = i
			break
	if ind > f:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	k0 = s.rfind('00')
	k1 = s.find('11')
	f = False
	if k1 == -1 or k0 == -1 or k0 < k1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	c = 0
	if len(s) <= 3:
		print('YES')
		c = 3
		s = ''
	s += '44'
	for i in range(len(s) - 2):
		if c == 1:
			break
		if s[i:i + 2] == '11':
			for j in range(i, len(s)):
				if s[j:j + 2] == '00':
					print('NO')
					c = 1
					break
	if c == 0:
		print('YES')


for _ in range(int(input())):
	s = input()
	f = -1
	g = -1
	for i in range(1, len(s)):
		if s[i] == '1' and s[i - 1] == s[i]:
			if f > -1:
				continue
			f = i - 1
		elif s[i] == '0' and s[i - 1] == s[i]:
			g = i - 1
	if g > f and f != -1 and (g != -1):
		print('NO')
	else:
		print('YES')


for _ in ' ' * int(input()):
	s = input()
	print('NYOE S'[s.find('00', s.find('11')) == -1::2])


t = int(input())
ans = []
for _ in range(t):
	s = input()
	a = s.find('00')
	b = s.find('11')
	if a == -1 or b == -1:
		ans.append('YES')
		continue
	if s.find('00', b) == -1:
		ans.append('YES')
		continue
	ans.append('NO')
for i in ans:
	print(i)


for t in range(int(input())):
	s = input()
	if '11' in s and '00' in s and (s.find('11') < s.rfind('00')):
		print('NO')
	else:
		print('YES')


def main(s):
	for i in range(1, len(s)):
		if s[i - 1] == s[i] == '1':
			break
	else:
		print('YES')
		return
	for j in range(i + 2, len(s)):
		if s[j - 1] == s[j] == '0':
			print('NO')
			return
	print('YES')
nn = int(input())
for _ in range(nn):
	main(input())


for q in range(int(input())):
	n = input()
	s = 0
	s1 = 0
	p = 0
	l = len(n)
	for i in range(l - 1, 0, -1):
		if n[i] == '0' and n[i - 1] == '0':
			s = 1
			p = i - 1
			break
	for i in range(p, 0, -1):
		if n[i] == '1' and n[i - 1] == '1':
			s1 = 1
			break
	if s1 == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	a = input()
	b = a.find('11') + 1
	c = a.rfind('00') + 1
	if b and c and (b < c):
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	a = len(s)
	b = s.find('11')
	d = s.rfind('00')
	print('NO' if b != -1 and d != -1 and (b < d) else 'YES')


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	s = input().strip()
	n = len(s)
	occ1 = -1
	for i in range(n - 1):
		if int(s[i]) and int(s[i + 1]):
			occ1 = i
			break
	if occ1 == -1:
		print('yes')
		continue
	occ2 = -1
	for i in range(n - 1):
		if not int(s[i]) and (not int(s[i + 1])):
			occ2 = i
	if occ2 == -1 or occ1 > occ2:
		print('yes')
	else:
		print('no')


t = int(input())
for _ in range(t):
	s = input().strip()
	dp = [0, 0]
	for c in s:
		if c == '0':
			dp = [2 * min(dp), dp[0]]
		elif c == '1':
			dp = [2 if min(dp) >= 2 else 1, dp[0]]
	if min(dp) < 2:
		print('YES')
	else:
		print('NO')


from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	ss = input()
	sp = ss.find('11')
	if sp == -1:
		print('YES')
	elif ss.find('00', sp) != -1:
		print('NO')
	else:
		print('YES')

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


T = int(input())
for _ in range(T):
	a = input()
	b = a[::-1]
	N = len(a)
	if '11' in a and '00' in b:
		if a.index('11') <= N - b.index('00') - 2:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


tc = int(input())
while tc > 0:
	s = input()
	l = len(s)
	Zero = []
	for i in range(l):
		if s[i] == '0':
			Zero.append(i)
	flag = True
	n = len(Zero)
	i = n - 1
	while i >= 0:
		if Zero[i] - Zero[i - 1] == 1:
			flag = False
			break
		else:
			i -= 1
	if flag == True:
		print('YES')
	else:
		i = Zero[i]
		One = []
		while i >= 0:
			if s[i] == '1':
				One.append(i)
			i -= 1
		ff = True
		for i in range(len(One) - 1):
			if abs(One[i] - One[i + 1]) == 1:
				ff = False
		if ff == True:
			print('YES')
		else:
			print('NO')
	tc -= 1


t = int(input())
for i in range(t):
	s = input()
	a = False
	for i in range(1, len(s)):
		if s[i] == s[i - 1] and s[i] == '1':
			a = True
		if a and s[i] == s[i - 1] and (s[i] == '0'):
			print('NO')
			break
	else:
		print('YES')


tc = int(input())
while tc > 0:
	tc -= 1
	s = input()
	pos = s.find('11')
	poss_0 = s[pos:].find('00')
	if poss_0 != -1:
		print('NO')
	else:
		print('YES')


from typing import List

def get_input() -> List[List[int]]:
	n = eval(input())
	ret = []
	for i in range(n):
		li = []
		a = input()
		for j in range(len(a)):
			li.append(int(a[j]))
		ret.append(li)
	return ret

def solve(case: List[int]):
	n = len(case)
	if n <= 3:
		return True
	idx = n - 1
	for i in range(1, n - 1):
		if case[i] == 1 and case[i - 1] == 1 and (case[i + 1] == 0):
			idx = i
			break
	for i in range(idx + 1, n - 1):
		if case[i] == 0 and case[i + 1] == 0:
			return False
	return True

def print_result(ans) -> None:
	if ans:
		print('YES')
	else:
		print('NO')

def solution() -> None:
	cases = get_input()
	for case in cases:
		print_result(solve(case))
solution()


from math import gcd
inp = int(input())
for _ in range(inp):
	s = input()
	i = s.find('11')
	j = s.rfind('00')
	if i != -1 and j != -1 and (i < j):
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	t = s.find('11')
	r = s[t:].find('00')
	if r != -1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	n = len(s)
	f = [0] * n
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			f[i] = s[i] == '0'
			continue
		f[i] = f[i + 1] + (s[i] == '0')
	if f[0] == 0 or f[0] == n:
		print('YES')
	else:
		i = 0
		flag = 0
		a = 0
		while i < n:
			if s[i] == '1':
				i += 1
				if i < n and s[i] == '1' and (f[i] != 0):
					j = i + 1
					while j < n:
						if s[j] == '0' and j + 1 < n and (s[j + 1] == '0'):
							flag = 1
							break
						j += 1
					a = 1
					break
				if i < n and f[i] <= 1:
					a = 1
					break
			if a == 1:
				break
			i += 1
		if flag == 1:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	s = input()
	p = -2
	flag = True
	for i in range(len(s)):
		if s[i] == '0':
			if i > p + 1:
				p = i
			else:
				flag = False
				break
	if flag:
		print('YES')
	else:
		p = -2
		flag = True
		for i in range(len(s)):
			if s[i] == '1':
				if i > p + 1:
					p = i
				else:
					flag = False
					break
		if flag:
			print('YES')
		else:
			flag = True
			for j in range(p, len(s)):
				if s[j] == '0':
					if j > p + 1:
						p = j
					else:
						flag = False
						break
			if flag:
				print('YES')
			else:
				print('NO')


import os
import math
import functools
true = True
false = False
from functools import reduce
is_dev = 'vscode' in os.environ
if is_dev:
	inF = open('in.txt', 'r')
	outF = open('out.txt', 'w')

def ins():
	return list(map(int, input_().split(' ')))

def inss():
	return list(input_().split(' '))

def input_():
	if is_dev:
		return inF.readline()[:-1]
	else:
		return input()

def ranin():
	return range(int(input_()))

def print_(data):
	if is_dev:
		outF.write(str(data) + '\n')
	else:
		print(data)
epsilon = 1e-07

@functools.lru_cache()
def solve(s, is_z=True, prev_remove=False):
	if s == '':
		return True
	if s[0] == '0':
		if prev_remove:
			if is_z:
				return solve(s[1:], True, False)
			else:
				return False
		elif is_z:
			return solve(s[1:], True, False)
		else:
			return solve(s[1:], False, True)
	elif not is_z:
		return solve(s[1:], False, False)
	elif prev_remove:
		return solve(s[1:], False, False)
	else:
		return solve(s[1:], False, False) or solve(s[1:], True, True)
for _ in ranin():
	s = input_()
	if solve(s):
		print_('YES')
	else:
		print_('NO')
if is_dev:
	outF.close()

	def compare_file():
		print(open('out.txt', 'r').read() == open('outactual.txt', 'r').read())
	compare_file()


for _ in range(int(input())):
	a = input()
	if a.find('11') < a.rfind('00') and a.find('11') >= 0 and (a.rfind('00') >= 0):
		print('NO')
	else:
		print('YES')


def solve(s):
	a = {}
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			continue
		if s[i] in a:
			a[s[i]].append(i)
		else:
			a[s[i]] = [i]
	if '0' not in a or '1' not in a:
		return True
	return a['0'][-1] < a['1'][0]
t = int(input())
for _ in range(t):
	s = input()
	print('YES' if solve(s) else 'NO')


from sys import stdin, stdout
from collections import deque
import bisect
R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))
output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))
import math
T = int(input())
for _ in range(T):
	s = input()
	one = -1
	ze = -1
	for i in range(0, max(0, len(s) - 1)):
		if s[i] == '1' and s[i + 1] == '1':
			one = i
			break
	for i in range(0, max(0, len(s) - 1)):
		if s[i] == '0' and s[i + 1] == '0':
			ze = i
	if one != -1 and ze != -1 and (one < ze):
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	s = input()
	i = s.find('11')
	if not i == -1:
		j = s.find('00', i, len(s))
		if j == -1:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


import sys

def main():
	inp = sys.stdin.read().strip().split('\n')[1:]
	out = []
	for s in inp:
		t = s.replace('10', '')
		out.append(('YES', 'NO')[list(t) != sorted(t)])
	return out
print(*main(), sep='\n')


cases = int(input())
while cases:
	cases -= 1
	s = input()
	if '00' in s and '11' in s:
		if s.index('11') < s.rindex('00'):
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


t = int(input())
while t:
	t -= 1
	s = input()
	flag = True
	i1 = s.find('11')
	if i1 != -1:
		if s[i1:].find('00') != -1:
			print('NO')
			continue
	print('YES')


t = int(input())
for _ in range(t):
	s = input()
	countone = 0
	counttwo = 0
	posione = []
	posizero = []
	for i in range(len(s)):
		if s[i] == '1':
			countone += 1
			counttwo = 0
			if countone == 2:
				posione.append(i)
		elif s[i] == '0':
			counttwo += 1
			countone = 0
			if counttwo == 2:
				posizero.append(i)
	if len(posione) > 0 and len(posizero) > 0 and (posizero[-1] > posione[0]):
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	a = input()
	if '11' in a and '00' in a[a.index('11'):]:
		print('NO')
	else:
		print('YES')


T = int(input())
for x in range(T):
	s = input()
	s1 = ''
	i = 0
	n = len(s)
	ans = ''
	l = list(s)
	l.sort()
	for p in l:
		s1 = s1 + p
	if s == s1:
		ans = 'YES'
	else:
		for y in range(1, n):
			if s[y - 1] == '1' and s[y] == '1':
				i = y
				break
		if i == 0 or i == n - 1:
			ans = 'YES'
		elif i + 1 == n - 1:
			ans = 'YES'
		else:
			for z in range(i + 2, n):
				if s[z - 1] == '0' and s[z] == '0':
					ans = 'NO'
					break
				else:
					ans = 'YES'
	print(ans)


for u in range(int(input())):
	s = input()
	a = -1
	if '11' in s:
		a = s.index('11')
	b = -1
	if '00' in s:
		b = len(s) - 1 - s[::-1].index('00')
	if a != -1 and b != -1 and (a < b):
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	zoz = []
	for j in range(len(s)):
		zoz.append(int(s[len(s) - j - 1]))
	dn = False
	pn = False
	c = 0
	for j in zoz:
		if pn == True and j == 0:
			dn = True
		elif pn == False and j == 1 and (dn == True):
			c = 1
		if j == 0:
			pn = True
		else:
			pn = False
	if c == 1:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()[:-1]
	if s == ''.join(sorted(s)):
		print('YES')
		continue

	def check(s0, x):
		n = len(s0)
		cand = [i for i in range(n) if s0[i] == x]
		flag = 1
		for (a, b) in zip(cand, cand[1:]):
			if b - a == 1:
				flag = 0
				break
		return flag
	n = len(s)
	for i in range(n + 1):
		if check(s[:i], '1') and check(s[i:], '0'):
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	ind11 = s.find('11')
	ind00 = s[::-1].find('00')
	if ind00 != -1:
		ind00 = len(s) - ind00 - 1
	if ind11 >= ind00 or ind11 == -1:
		print('YES')
	else:
		print('NO')


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
for _ in range(int(inp())):
	s = inp()
	flg = False
	flg2 = True
	for i in range(len(s) - 1):
		if s[i] == '1' and s[i + 1] == '1':
			flg = True
		if s[i] == '0' and s[i + 1] == '0':
			if flg:
				flg2 = False
				break
	print('YES' if flg2 else 'NO')


t = int(input())
for tt in range(t):
	s = input()
	n = len(s)
	(k, l) = (n, n)
	for i in range(1, n):
		if s[i] == '1' and s[i - 1] == '1':
			k = i
			break
	for i in range(1, n):
		if s[-i] == '0' and s[-i - 1] == '0':
			l = i
			break
	if k + l < n:
		print('NO')
	else:
		print('YES')


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	s = input()
	n = len(s)
	l = []
	for i in range(n):
		prev = next = ' '
		if i - 1 >= 0:
			prev = s[i - 1]
		if i + 1 < n:
			next = s[i + 1]
		if s[i] != prev and s[i] != next:
			continue
		else:
			l += [s[i]]
	print('YES' if sorted(l) == l else 'NO')


t = int(input())
for _ in range(t):
	s = input()
	st1 = len(s)
	for i in range(1, len(s)):
		if s[i] == s[i - 1] == '1':
			st1 = i
			break
	st2 = 0
	for i in range(len(s) - 1, 1, -1):
		if s[i] == s[i - 1] == '0':
			st2 = i
			break
	if st2 > st1:
		print('no')
	else:
		print('yes')


def solve():
	s = input()
	ok = False
	n = len(s)
	for i in range(1, n):
		if s[i] == '1' and s[i - 1] == '1':
			ok = True
		elif s[i] == '0' and ok == True:
			if i + 1 < n and s[i + 1] == '0':
				print('NO')
				return
	print('YES')
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	s = input().rstrip()
	n = len(s)
	idx = -1
	f = 0
	for i in range(n - 1):
		if s[i] == '1':
			if s[i + 1] == '1':
				idx = i
				break
	if idx != -1:
		for i in range(idx + 1, n - 1):
			if s[i] == '0':
				if s[i + 1] == '0':
					f = 1
					break
		if f == 1:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for j in range(1):
	pass
for _ in range(int(input())):
	s = input()
	if s.find('11') < s.rfind('00') and (s.find('11') != -1 and s.rfind('00') != -1):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	a = input()
	i = 0
	c = 0
	if '11' in a:
		x = a.index('11') + 2
		if x < len(a) and '00' in a[x:]:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


import sys

def solve(s):
	n = len(s)
	ans = False
	for i in range(n):
		local_ans = True
		removal = []
		for j in range(i):
			if s[j] == '1':
				removal.append(j)
		for j in range(i, n):
			if s[j] == '0':
				removal.append(j)
		for i in range(1, len(removal)):
			if removal[i - 1] + 1 >= removal[i]:
				local_ans = False
		ans |= local_ans
	return 'YES' if ans else 'NO'
if 1 == 2:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
T = int(input())
for _ in range(T):
	s = input()
	print(solve(s))


for i in range(int(input())):
	s = input()
	if s.count('0') == 0 or s.count('1') == 0:
		print('YES')
		continue
	try:
		one = s.index('11')
		zero = len(s) - 1 - s[::-1].index('00')
		if one < zero:
			print('NO')
		else:
			print('YES')
	except:
		print('YES')


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_right

def main():
	s = [int(c) for c in input()]
	n = len(s)
	pr1 = False
	pv = False
	k = -1
	for i in range(n):
		if s[i] == 1:
			if pv == True:
				pr1 = True
			else:
				pv = True
		else:
			pv = False
			if pr1 == True:
				k = i
				break
	if k == -1:
		print('YES')
		return
	pv = True
	for i in range(k + 1, n):
		if i > 0 and s[i] == s[i - 1] == 0:
			print('NO')
			return
	print('YES')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


t = int(input())
for test_case in range(t):
	binary = input()
	index = binary.find('11')
	if index < 0:
		print('YES')
		continue
	sub_binary = binary[index + 2:]
	if sub_binary.find('00') >= 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	flag = False
	if '00' in s and '11' in s:
		if s.rfind('00') > s.find('11'):
			flag = True
	if flag:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	s = list(input())
	s.remove('\n')
	start = -1
	for i in range(1, len(s)):
		if s[i] == '1' and s[i - 1] == '1':
			start = i + 1
			break
	if start == -1:
		print('YES')
	else:
		ans = True
		for i in range(start + 1, len(s)):
			if s[i] == '0' and s[i - 1] == '0':
				ans = False
				break
		if ans:
			print('YES')
		else:
			print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	ans1 = n
	for i in range(n - 1):
		if s[i] == '1' and s[i + 1] == '1':
			ans1 = i
			break
	s = s[::-1]
	ans2 = 0
	for i in range(n - 1):
		if s[i] == '0' and s[i + 1] == '0':
			ans2 = n - i
			break
	if ans1 >= ans2:
		print('YES')
	else:
		print('NO')


il = lambda : list(map(int, input().split()))
iin = lambda : map(int, input().split())
ii = lambda : int(input())
for _ in range(ii()):
	s = input()
	(x, y) = (-1, -1)
	flag = 0
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			if s[i] == '0':
				y = i - 1
			if s[i] == '1':
				x = i - 1
		if (x != -1 and y != -1) and x < y:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


def f(s):
	f1 = s.find('11')
	if f1 == -1:
		return 'YES'
	else:
		f2 = s.find('00', f1)
		if f2 == -1:
			return 'YES'
		else:
			return 'NO'
t = int(input())
l = []
for i in range(t):
	d = str(input())
	s = f(d)
	l.append(s)
for y in l:
	print(y)


T = int(input())
r = 1
while r <= T:
	s = input()
	ones = -1
	zeros = -1
	for i in range(len(s) - 1):
		if s[i] == '0' and s[i + 1] == '0':
			zeros = i
		if s[i] == '1' and s[i + 1] == '1' and (ones == -1):
			ones = i
	if ones >= 0 and ones < zeros:
		print('NO')
	else:
		print('YES')
	r += 1


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	s = ips()
	s = list(s)
	cur = []
	main = False
	n = len(s)
	for i in range(n):
		left = s[:i]
		right = s[i:]
		cur = []
		val = None
		flag = True
		count = 0
		for j in range(0, i, 1):
			if s[j] == '1':
				count += 1
				if val == None:
					val = j
				else:
					if j - 1 == val:
						flag = False
						break
					val = j
			else:
				cur.append('0')
		for j in range(i, n, 1):
			if s[j] == '0':
				count += 1
				if val == None:
					val = j
				else:
					if j - 1 == val:
						flag = False
						break
					val = j
			else:
				cur.append('1')
		if flag and count > 0:
			main = True
			break
	if main:
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def solve(__=1):
	for _ in range(__):
		s = input()
		if '11' in s and '00' in s:
			if '00' in s[s.index('11'):]:
				print('NO')
			else:
				print('YES')
		else:
			print('YES')
solve(inp())


t = int(input())
for i in range(t):
	s = input()
	if '00' in s and '11' in s and (s.index('11') < len(s) - s[::-1].index('00')):
		print('NO')
	else:
		print('YES')


import sys
import math
import bisect
import functools
from functools import lru_cache
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from heapq import heappush, heappop, heapify
from collections import defaultdict as dd
from collections import Counter as cc
from bisect import bisect_left as bl
from bisect import bisect_right as br

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
sys.setrecursionlimit(100000000)
intinp = lambda : int(input().strip())
stripinp = lambda : input().strip()
fltarr = lambda : list(map(float, input().strip().split()))
intarr = lambda : list(map(int, input().strip().split()))
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
MOD = 1000000007

@lru_cache(None)
def help(need, left):
	if left == '':
		return True
	if len(left) > 1:
		if left[0] == '0' and need and (left[1] == '1'):
			return help(need, left[2:])
		elif left[1] == '0' and need and (left[0] == '1'):
			return help(need, left[1:])
		elif need and left[1] == '0' and (left[0] == '0'):
			return False
		else:
			return help(need or int(left[1]), left[2:]) or help(need or int(left[0]), left[1:])
	elif left[0] == '0' and need:
		return help(need, left[1:])
	else:
		return help(need or int(left[0]), left[1:]) or help(need, left[1:])
num_cases = intinp()
for _ in range(num_cases):
	s = stripinp()
	if help(0, s):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	first = s.find('11')
	last = s.rfind('00')
	if first != -1 and last != -1 and (first < last):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = list(input())
	ans = 'YES'
	o = 0
	z = 0
	for i in range(len(s) - 1):
		if s[i] == '1' and s[i + 1] == '1':
			o = 1
		elif s[i] == '0' and s[i + 1] == '0' and (o == 1):
			ans = 'NO'
	print(ans)


t = int(input())
for _ in range(t):
	a = input().strip()
	L = len(a)
	if '11' not in a:
		print('YES')
	else:
		for i in range(L - 1):
			if a[i] == '1' and a[i + 1] == '1':
				if '00' in a[i + 2:L]:
					print('NO')
				else:
					print('YES')
				break


for _ in range(int(input())):
	s = input()
	p = -1
	if s == '0' * len(s) or s == '1' * len(s):
		print('YES')
		continue
	for i in range(len(s)):
		if s[i] == '1':
			p = i
			break
	if p == -1:
		p = len(s) - 1
	i = p
	f = 0
	while i < len(s) - 1:
		if s[i] == '1' and s[i + 1] == '1':
			p = i + 2
			f = 1
			break
		elif s[i] == '1' and s[i + 1] == '0':
			i += 2
		else:
			i += 1
	if f == 0:
		p = i
	ans = s[p:]
	if ans.find('00') != -1:
		print('NO')
	else:
		print('YES')


import os
import sys
from io import BytesIO, IOBase
import math
BUFSIZE = 8192
from collections import Counter

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for _ in range(t):
	s = input()
	f = 0
	for i in range(len(s)):
		r = 1
		for j in range(1, i):
			if s[j] == s[j - 1] == '1':
				r = 0
				break
		for j in range(i + 2, len(s)):
			if s[j] == s[j - 1] == '0':
				r = 0
				break
		if r == 1:
			f = 1
			break
	if f:
		print('YES')
	else:
		print('NO')


def checkifcanbesorted():
	s = input()
	a1 = s.split('11', 1)
	if len(a1) == 1:
		return 'YES'
	a1 = a1[1].split('00', 1)
	return 'YES' if len(a1) == 1 else 'NO'
n = int(input())
for i in range(n):
	print(checkifcanbesorted())


from itertools import permutations as perm
from fractions import Fraction
from collections import *
from sys import stdin
from bisect import *
from heapq import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
fi = []
(t,) = gil()
for _ in range(t):
	s = gbs()
	n = len(s)
	f = True
	for i in range(1, n):
		f &= s[i] >= s[i - 1]
	if f:
		print('yes')
		continue
	rem_int = 1
	prev = -2
	f = True
	for i in range(n):
		if s[i] == rem_int:
			if i > prev + 1:
				prev = i
			elif rem_int:
				rem_int = 0
				prev = -1
			else:
				f &= False
				break
	print('yes' if f else 'no')


import sys, math
sys.setrecursionlimit(10 ** 8)

def find(s):
	if s.count('00') == 0 or s.count('11') == 0:
		return 'YES'
	if s.index('11') < s.rindex('00'):
		return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	s = input()
	print(find(s))


import sys

def input():
	return sys.stdin.readline().rstrip()

def slv():
	s = input()
	a = []
	for c in s:
		a.append(int(c))
	if all((elem == 1 for elem in a)) or all((elem == 0 for elem in a)):
		print('Yes')
		return
	zero_cnt = a.count(0)
	for c in range(zero_cnt + 1):
		zero_c = 0
		l = []
		for (i, v) in enumerate(a):
			if zero_c >= c:
				if v == 0:
					l.append(i)
			elif v == 1:
				l.append(i)
			else:
				zero_c += 1
		if len(l) < 2 or all((l[i + 1] - l[i] > 1 for i in range(len(l) - 1))):
			print('Yes')
			return
	print('No')
	return

def main():
	t = int(input())
	for _ in range(t):
		slv()
	return
main()


def answer(s):
	if len(s) == 2:
		return 'YES'
	ssorted = sorted(s)
	if ssorted == s:
		return 'YES'
	two_ones = False
	two_ones_addr = -1
	two_zeros = False
	two_zeros_addr = -1
	for i in range(1, len(s)):
		if s[i] == s[i - 1] and s[i] == '1' and (two_ones == False):
			two_ones_addr = i
			two_ones = True
		if s[i] == s[i - 1] and s[i] == '0':
			two_zeros_addr = i
	if two_ones and two_ones_addr < two_zeros_addr:
		return 'NO'
	return 'YES'

def main():
	t = int(input())
	s = [0] * t
	for j in range(t):
		s[j] = input()
	for j in range(t):
		print(answer(s[j]))
main()


t = int(input())
while t:
	s = input()
	pos = s.find('11')
	if pos == -1:
		print('YES')
	elif s.find('00', pos) == -1:
		print('YES')
	else:
		print('NO')
	t -= 1


import sys
input = sys.stdin.readline

def solution(s):
	n = len(s)
	last_position_double_0 = -1
	first_position_double_1 = n + 1
	for pos in range(n - 1):
		if s[pos] == s[pos + 1] == '0':
			last_position_double_0 = pos
	for pos in range(n - 1, 0, -1):
		if s[pos] == s[pos - 1] == '1':
			first_position_double_1 = pos - 1
	if last_position_double_0 < first_position_double_1:
		print('YES')
	else:
		print('NO')
T = int(input())
for t in range(T):
	s = input().strip()
	solution(s)