You are given a binary string S of length N. Your task is to check if there exists a [substring] of S which is the binary representation of a [prime number].

Formally, check if there exist integers L and R such that 1 ≤ L ≤ R ≤ N, and the substring S_{L} S_{L+1} S_{L+2} \ldots S_{R}, when treated as a binary integer, is prime.

Print "Yes" if such a substring exists, and "No" if it doesn't.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each testcase consists of a single line of input, containing a binary string S.

------ Output Format ------ 

For each test case, output a single line containing one string — "Yes" or "No", the answer to the problem.

You may print each character of the answer in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

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

$1 ≤ T ≤ 2.5 \cdot 10^{4}$
$|S| ≤ 10^{5}$ 
- The sum of $|S|$ over all tests does not exceed $3 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (30 points):
$1 ≤ T ≤ 10^{3}$
$|S| ≤ 10$
 
Subtask 2 (70 points):
Original constraints

----- Sample Input 1 ------ 
3
1
111
101101
----- Sample Output 1 ------ 
No
Yes
Yes
----- explanation 1 ------ 
Test case $1$: There is only one substring, namely "1", and it isn't prime.

Test case $2$: The substrings of the given string are $\{$"1", "11", "111", "1", "11", "1"$\}$. Of these, "111" which represents $7$ in binary, and "11" which represents $3$ in binary, are primes.

Test case $3$: One of the substrings of the string is "1101", which is the binary representation of $13$ — a prime.

Difficulty: MEDIUM

Starter code:

Solutions:
for _ in range(int(input())):
	s = input()
	n = len(s)
	if n == 1:
		print('No')
		continue
	count = 0
	pos = -1
	i = 0
	while i < n:
		if s[i] == '1':
			count += 1
			pos = i + 1
		i += 1
	if count == 0 or (count == 1 and pos == n):
		print('No')
	else:
		print('Yes')


def prime(n):
	if n > 1:
		b = True
		for i in range(2, int(n / 2) + 1):
			if n % i == 0:
				b = False
				break
	else:
		b = False
	return b

def bina(binary):
	(decimal, i) = (0, 0)
	while binary != 0:
		dec = binary % 10
		decimal = decimal + dec * pow(2, i)
		binary = binary // 10
		i += 1
	return decimal

def main():
	t = int(input())
	for z in range(t):
		b = int(input())
		s = str(b)
		i = 0
		l = []
		flag = 0
		while i < len(s) and flag == 0:
			s1 = s[i]
			j = i + 1
			while j < len(s) and flag == 0:
				s1 = s1 + s[j]
				if prime(bina(int(s1))):
					flag = 1
				j = j + 1
			i = i + 1
		if flag == 1:
			print('Yes')
		else:
			print('No')
main()


for _ in range(int(input())):
	n = str(input())
	if n.find('10') != -1 or n.find('11') != -1:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	a = input()
	if '11' in a or '10' in a:
		print('Yes')
	else:
		print('No')


import math

def check_prime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
t = int(input())
j = False
for i in range(t):
	s = input()
	if len(s) == 1:
		print('No')
	elif s.find('11') != -1 or s.find('10') != -1:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	s = input()
	if '10' in s or '11' in s:
		print('Yes')
	else:
		print('No')


def solve(s, n):
	if n == 1:
		return 'No'
	for i in range(1, n):
		if s[i] == '1' and s[i - 1] == '1':
			return 'Yes'
		if s[i] == '0' and s[i - 1] == '1':
			return 'Yes'
	return 'No'
for _ in range(int(input())):
	s = input()
	n = len(s)
	print(solve(s, n))


for _ in range(int(input())):
	binary = input()
	if '10' in binary or '11' in binary:
		print('Yes')
	else:
		print('No')


tests = int(input())
for i in range(tests):
	string = input()
	length = len(string)
	ans = 'No'
	for j in range(length):
		if string[j] == '1' and j != length - 1:
			ans = 'Yes'
			break
	print(ans)


for tc in range(int(input())):
	a = input()
	if int(a) <= 1:
		print('No')
	else:
		print('Yes')


t = int(input())
for k in range(t):
	n = input()
	if '10' in n or '11' in n:
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	b = input()
	if '11' in b or '10' in b or '111' in b:
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	s = input()
	s = s[:len(s) - 1]
	if s.count('1') > 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	s = input()
	s1 = s[:len(s) - 1]
	if '1' in s1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = input()
	if '11' in n:
		print('Yes')
	elif '10' in n:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	s = input()
	x = s.find('11')
	y = s.find('10')
	if x != -1 or y != -1:
		print('Yes')
	else:
		print('No')


tc = int(input())
for _ in range(tc):
	n = str(input())
	str1 = n[:len(n) - 1]
	if str1.count('1') > 0:
		print('Yes')
	else:
		print('No')