Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Bear Limak has a string S.
Each character of S is a digit '0' or '1'.

Help Limak and check if all the '1' digits form a single non-empty segment (consecutive subsequence) in the string. For each test case, print "YES" or "NO" accordingly.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The only line of each test case contains one string S, consisting of digits '0' and '1' only.

------ Output ------ 

For each test case, output a single line containing the answer — "YES" if all the '1' digits form a single non-empty segment, and "NO" otherwise. Don't print the quotes.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ |S| ≤ 10^{5} (here, |S| denotes the length of S)$

------ Subtasks ------ 

$Subtask #1 (50 points): 1 ≤ |S| ≤ 50$
$Subtask #2 (50 points): Original constraints.$

----- Sample Input 1 ------ 
6

001111110

00110011

000

1111

101010101

101111111111
----- Sample Output 1 ------ 
YES

NO

NO

YES

NO

NO
----- explanation 1 ------ 
The answer is "YES" for strings 001111110 and 1111.

The answer is "NO" for 00110011 because the '1' digits form two disjoint segments (while they should all be consecutive, with no '0' digits between them).

The answer is "NO" for 000 because the segment formed by the '1' digits must be non-empty (as written in the statement).

Source: codechef | Difficulty: EASY
Tags: Implementation


Solutions:
for _ in range(int(input())):
	s = input()
	if s.count('1') != 0:
		c1 = s.count('1')
		st = s.index('1')
		c0 = s[st:c1 + st].count('0')
		if c0 >= 1:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


for i in range(int(input())):
	BS = input()
	count = 1
	for i in range(1, len(BS)):
		prev = BS[i - 1]
		curr = BS[i]
		if prev == '1' and curr == '1':
			count += 1
		else:
			count += 0
	print('YES' if count == BS.count('1') else 'NO')


for i in range(int(input())):
	s = input()
	c1 = s.count('1')
	if s.count('1') == 0:
		print('NO')
		continue
	ci = s.index('1')
	c0 = s[ci:ci + c1].count('0')
	print('NO' if c0 else 'YES')


for _ in range(int(input())):
	a = input()
	if a.count('1') == 0:
		print('NO')
		continue
	k1 = a.count('1')
	start = a.index('1')
	k0 = a[start:k1 + start].count('0')
	print('NO' if k0 else 'YES')


for _ in range(int(input())):
	h = input()
	if h.count('1') == 0:
		print('NO')
		continue
	cnt1 = h.count('1')
	start = h.index('1')
	cnt0 = h[start:cnt1 + start].count('0')
	print('NO' if cnt0 else 'YES')


t = int(input())
for _ in range(t):
	s = input()
	ans = True
	count_1 = s.count('1')
	if count_1 == 0:
		print('NO')
	else:
		count = 0
		for i in range(len(s)):
			if s[i] == '1':
				count += 1
			elif count < count_1 and count > 0:
				ans = False
				break
			elif count == 0:
				pass
			else:
				break
		if ans:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	s = input()
	x = s.count('1')
	if str(x * '1') in s:
		if s.count('1') >= 1:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for i in range(int(input())):
	s = input().strip()
	(c, d) = (s.find('1'), s.rfind('1'))
	if '0' in s[c:d + 1] or '1' not in s:
		print('NO')
	else:
		print('YES')


goals = int(input())
for distractions in range(goals):
	wife = input().strip()
	(aim, stress) = (wife.find('1'), wife.rfind('1'))
	if '0' in wife[aim:stress + 1] or '1' not in wife:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input().strip('0')
	if '1' in s:
		if '0' in s[s.index('1'):]:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


t = int(input())
while t:
	s = input()
	n = int(len(s))
	flag = bool(1)
	for i in range(n):
		if s[i] == '1':
			flag = 0
			break
	if i == n - 1:
		flag = 0
	elif i != n - 1:
		for j in range(i, n):
			if s[j] == '0':
				flag = 0
				break
			else:
				flag = 1
	if j == n - 1:
		flag = 1
	if j != n - 1:
		for k in range(j, n):
			if s[k] == '1':
				flag = 0
				break
			else:
				flag = 1
	if flag == 0:
		print('NO')
	else:
		print('YES')
	t = t - 1


t = int(input())
while t:
	s = input()
	n = len(s)
	checker = int(5)
	start = int(0)
	end = int(0)
	if s[0] == '1':
		checker = 2
	for i in range(1, n):
		if s[i] == '1' and s[i - 1] == '0':
			checker = 0
			start += 1
			continue
		if s[i] == '0' and s[i - 1] == '1':
			checker = 1
			end += 1
	if start == 1 and end == 1 and (checker == 1):
		print('YES')
	elif start == 1 and end == 1 and (checker == 0):
		print('NO')
	elif start == 1 and end == 0:
		print('YES')
	elif start == 0 and end == 1:
		print('YES')
	elif checker == 2:
		print('YES')
	else:
		print('NO')
	t = t - 1


t = int(input())
for _ in range(t):
	s = input()
	c = 1
	for i in range(len(s) - 1):
		if s[i] == '1' and s[i + 1] == '1':
			c += 1
	if c == s.count('1'):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	s = input()
	if s.count('1') == 0:
		print('NO')
		continue
	for i in range(s.index('1'), s.index('1') + s.count('1')):
		if s[i] == '0':
			print('NO')
			break
	else:
		print('YES')


import itertools
for _ in range(int(input())):
	s = input().strip()
	d = dict()
	for x in s:
		d[x] = d.get(x, 0) + 1
	i = itertools.groupby(s)
	y = 0
	for (k, g) in i:
		a = len(list(g))
		if k == '1' and a == d['1']:
			y = 1
			print('YES')
			break
	if y == 0:
		print('NO')


for i in range(int(input())):
	l = list(input())
	if '1' not in l:
		print('NO')
	else:
		x = l.index('1')
		y = l.count('1')
		if l[x:x + y] == ['1'] * y:
			print('YES')
		else:
			print('NO')


t = int(input())
for tc in range(t):
	s = input()
	x = 0
	p = s.count('1')
	if p == 0:
		print('NO')
	else:
		for j in range(0, len(s)):
			if s[j] == '1':
				x += 1
			elif s[j] == '0' and x != 0:
				break
		if x == p:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	s = input()
	a = []
	for i in range(len(s)):
		if s[i] == '1':
			a.append(i)
	if len(a) == 0:
		print('NO')
	else:
		for i in range(len(a) - 1):
			if a[i + 1] == a[i] + 1:
				pass
			else:
				print('NO')
				break
		else:
			print('YES')


for i in range(int(input())):
	s = str(input())
	a = 0
	t = s.count('1')
	if t == 0:
		print('NO')
	else:
		for i in range(0, len(s)):
			if s[i] == '1':
				a += 1
			elif s[i] == '0' and a != 0:
				break
		if a == t:
			print('YES')
		else:
			print('NO')


for t in range(int(input())):
	s = input()
	lis = s.split('0')
	a = lis.count('')
	if len(lis) == a + 1:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	s = input()
	if s.count('1') == len(s):
		print('YES')
	elif s.count('0') == len(s):
		print('NO')
	else:
		lis = []
		for i in range(len(s)):
			if s[i] == '1':
				lis.append(i)
		if max(lis) - min(lis) == len(lis) - 1:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	s = input()
	l1 = s.split('0')
	a = l1.count('')
	if len(l1) == 1 + a:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	ind = 0
	c = 0
	a = 'YES'
	if s.count('1') == 0:
		a = 'NO'
	else:
		for i in range(len(s)):
			if s[i] == '1':
				if i != ind + 1 and c >= 1:
					a = 'NO'
					break
				else:
					ind = i
					c += 1
	print(a)


for _ in range(int(input())):
	s = input()
	count_1 = s.count('1')
	c = 0
	if '1' in s:
		for i in range(len(s) - 1):
			if s[i] == '1':
				if s[i] == s[i + 1]:
					c += 1
				else:
					break
		if c == count_1 - 1:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	S = input()
	ones = '1' * S.count('1')
	if ones == '':
		print('NO')
		continue
	print('YES') if ones in S else print('NO')


n = int(input())
for i in range(n):
	s = input()
	count = 0
	l = len(s)
	flag = True
	done = 'false'
	for i in range(l):
		if s[i] == '1':
			count = count + 1
	if count == 0:
		flag = False
	for j in range(l):
		if s[j] == '1' and done == 'false':
			done = 'true'
			for k in range(count):
				if s[k + j] == '0':
					flag = False
	if flag == True:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	flag = 0
	cnt = 0
	for i in range(len(s)):
		if s[i] == '1':
			flag = 1
		if flag == 1:
			if s[i] == '1':
				cnt += 1
			else:
				flag = 0
				break
	if s.count('1') == 0:
		print('NO')
	elif s.count('1') == cnt:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	l = list(s.split('0'))
	l = [x for x in l if x != '']
	if len(l) == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input().lstrip('0')
	s = s.rstrip('0')
	if not s or '0' in s:
		print('NO')
	else:
		print('YES')


def solve():
	global one_1, one_2
	one_1 = False
	one_2 = False
	for i in s:
		if '1' not in s:
			return 'NO'
		if i == '1':
			one_1 = True
		if one_1:
			if i == '0':
				one_2 = True
		if one_2:
			if i == '1':
				return 'NO'
	else:
		return 'YES'
for _ in range(int(input())):
	s = input()
	print(solve())


import re
for i in range(int(input())):
	s = input()
	l = re.findall('1+', s)
	if len(l) == 1:
		print('YES')
	else:
		print('NO')


import sys

def f():
	s = sys.stdin.readline()[:-1]
	if int(s) == 0:
		return 'NO\n'
	s = s.strip('0')
	if s.count('0') > 0:
		return 'NO\n'
	return 'YES\n'
for _ in range(int(sys.stdin.readline())):
	sys.stdout.write(f())


import sys

def f():
	s = int(sys.stdin.readline())
	if s == 0:
		return 'NO\n'
	s = str(s).rstrip('0')
	if s.count('0') > 0:
		return 'NO\n'
	return 'YES\n'
for _ in range(int(sys.stdin.readline())):
	sys.stdout.write(f())


T = int(input())
for _ in range(T):
	s = input()
	s = s.strip('0')
	if len(s) == 0:
		print('NO')
	else:
		for i in s:
			if i != '1':
				print('NO')
				break
		else:
			print('YES')


t = int(input())
while t:
	S = input().strip('0')
	if '0' not in S and '1' in S:
		print('YES')
	else:
		print('NO')
	t = t - 1


t = int(input())
for _ in range(t):
	s = str(input())
	x = s.strip('0')
	if len(x) == 0:
		print('NO')
	else:
		for i in x:
			if i != '1':
				print('NO')
				break
		else:
			print('YES')


for _ in range(int(input())):
	s = input()
	if s.count('1') == 0:
		print('NO')
		continue
	s = '0' + s + '0'
	if s.count('01') > 1 or s.count('10') > 1:
		print('NO')
	else:
		print('YES')


for v in range(int(input())):
	h = 0
	d = [int(e) for e in input()]
	for b in d:
		if b == 0:
			h += 1
		else:
			break
	for b in d[::-1]:
		if b == 0:
			h += 1
		else:
			break
	if d.count(0) > h or d.count(1) == 0:
		print('NO')
	else:
		print('YES')


T = int(input())
for i in range(T):
	S = input() + '0'
	A = len(S)
	(o, c) = (0, 1)
	for i in range(A - 1):
		if S[i] == '1':
			o += 1
		if S[i] == S[i + 1] == '1':
			c += 1
	if o == c:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	str = input()
	l_str = list(str)
	count_1 = l_str.count('1')
	count = 1
	j = 0
	while j < len(str):
		if str[j] == '1':
			for k in range(j + 1, len(str)):
				if str[k] == '1':
					count += 1
				else:
					break
				j = k
		j += 1
	if count_1 == count:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	count = 0
	flag = False
	for i in range(len(s)):
		if s[i] == '1':
			flag = True
		else:
			if flag:
				count += 1
			flag = False
	if s[len(s) - 1] == '1':
		count += 1
	if count != 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	val = 0
	for i in s:
		if i == '0' and val == 0:
			continue
		elif i == '1' and val == 0:
			val = 1
		elif val > 0 and i == '0':
			val = 2
		elif i == '1' and val == 1:
			continue
		elif i == '1' and val != 1:
			val = 0
			break
	if val == 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	s = input()
	s1 = s[::-1]
	if '1' not in s:
		print('NO')
		continue
	x = s.index('1')
	y = s1.index('1')
	m = len(s) - (y + 1)
	for i in range(x, m + 1):
		if s[i] == '0':
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	s = input() + '0'
	n = len(s)
	(o, c) = (0, 1)
	for i in range(n - 1):
		if s[i] == '1':
			o += 1
		if s[i] == s[i + 1] == '1':
			c += 1
	if o == c:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	count = 0
	flag = ''
	for i in s:
		if flag != '1' and i == '1':
			count += 1
			flag = '1'
		if flag != '0' and i == '0':
			flag = '0'
	if count == 0:
		print('NO')
	elif count == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	a = s.count('1')
	c = '1' * a
	if c in s and a > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	s = input()
	if '0' in s.strip('0'):
		print('NO')
	elif len(s.strip('0')) == 0:
		print('NO')
	else:
		print('YES')
	t -= 1


for _ in range(int(input(''))):
	s = list(map(int, input('')))
	n = len(s)
	l = 0
	for i in range(n):
		if s[i] == 1:
			a = i
			break
	for i in range(n - 1, -1, -1):
		if s[i] == 1:
			b = i
			break
	d = b - a + 1
	for j in s:
		l += j
	if l == d:
		print('YES')
	else:
		print('NO')


goals = int(input())
for distractions in range(goals):
	wife = input()
	life = 0
	death = 0
	for i in range(len(wife)):
		if wife[i] == '1':
			life += i
			break
	for i in range(len(wife) - 1, -1, -1):
		if wife[i] == '1':
			death += i
			break
	s = wife[life:death + 1]
	if '0' in s:
		print('NO')
	else:
		print('YES')


T = int(input())
for t in range(T):
	S = list((int(i) for i in input()))
	seg1 = []
	for i in range(len(S)):
		if S[i] == 1:
			seg1.append(i)
	count = 0
	for k in range(len(seg1) - 1):
		if seg1[k + 1] - seg1[k] != 1:
			count += 1
	if seg1 == [] or count != 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	count = 0
	c1 = s.count('1')
	s2 = '1' * c1
	if s2 in s and c1 > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	s.split()
	l = []
	c = 0
	for j in range(len(s)):
		if s[j] == '1':
			l.append(j)
			c += 1
	if len(l) == 0:
		print('NO')
	else:
		p = len(l) - 1
		k = l[p] - l[0] + 1
		if k == c:
			print('YES')
		else:
			print('NO')


for r in range(int(input())):
	s = input()
	found = False
	state = True
	c = 0
	for i in s:
		if i == '1' and (not found):
			found = True
		elif i == '0' and found:
			c = 1
		elif i == '1' and c == 1:
			state = False
	if state and found:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	S = input()
	one = S.count('1')
	try:
		i = S.index('1')
		for j in range(i, one + i):
			if S[j] == '0':
				print('NO')
				break
		else:
			print('YES')
	except:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	string = input()
	count = string.count('1')
	final = 0
	for i in string:
		if i == '1':
			final = final + 1
		else:
			final = 0
		if final == count:
			break
	if final == count and count != 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	c = 0
	for i in s:
		if i == '1':
			c += 1
	if c == 0:
		print('NO')
		continue
	k = s.split('0')
	m = c
	for i in k:
		if i == '' or i == '0':
			continue
		l = len(i)
		if l < m:
			m = l
	if m == c:
		print('YES')
	else:
		print('NO')