Chef is given a number in form of its binary representation S, having length N.

Determine if the number can be represented as a sum of exactly three non-negative powers of 2. Please refer to samples for further explanation.

Note that S will NOT contain leading zeros.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N, the length of the binary string.
- The next line contains the string S, the binary representation of a number.

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

For each test case, output YES if the number can be represented as sum of exactly three powers of 2.

You can print each character in uppercase or lowercase. For example YES, yes, Yes, and yES are all considered the same.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$S$ consists of $0$ and $1$ only, and has no leading zeros.
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
1
1
4
1001
5
11001
7
1101101

----- Sample Output 1 ------ 
NO
YES
YES
NO

----- explanation 1 ------ 
Test case $1$: It is not possible to represent the given number as a sum of exactly three powers of $2$.

Test case $2$: The given string $1001$ corresponds to the number $9$. We can represent $9$ as a sum of exactly three powers of $2$ as $9 = 2^{2} + 2^{2} + 2^{0}$.

Test case $3$: The given string $11001$ corresponds to the number $25$. We can represent $25$ as a sum of exactly three powers of $2$ as $25 = 2^{4} + 2^{3} + 2^{0}$.

Test case $4$: It is not possible to represent the given number as a sum of exactly three powers of $2$.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Mathematics


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	f = 0
	for i in range(len(b)):
		if b[i] == '1':
			f += 1
	if f == 2 or f == 3:
		print('YES')
	elif f == 1:
		if len(b) > 2:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	j = 0
	for i in s:
		if i == '1':
			j += 1
	if s == '1' or s == '10':
		print('NO')
	elif j <= 3:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.count('1') <= 3 and s != '1' and (s != '10'):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s == '1' or s == '10':
		print('NO')
	elif s.count('1') <= 3:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	ones = 0
	zeros = 0
	for i in s:
		if i == '1':
			ones += 1
		else:
			zeros += 1
	if ones == 2 or ones == 3:
		print('YES')
	elif ones == 1 and zeros >= 2:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	if s == '1' or s == '10':
		print('NO')
	else:
		c = s.count('1')
		if c <= 3:
			print('YES')
		else:
			print('NO')


t = int(input())
for zz in range(t):
	n = int(input())
	s = str(input())
	c = s.count('1')
	if s == '11':
		print('YES')
	elif c <= 3 and n >= 3:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	S = input()
	no1 = S.count('1')
	if N == 1:
		print('NO')
	elif no1 == 2 or no1 == 3:
		print('YES')
	elif N > 2 and (no1 == 1 and S.find('1') < N - 2):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	c = 0
	if s == '1' or s == '10' or s == '01':
		print('NO')
	else:
		while i < len(s):
			if s[i] == '1':
				c += 1
			i += 1
		if c <= 3:
			print('YES')
		else:
			print('NO')


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	if s == '1' or s == '10':
		print('NO')
	else:
		c = 0
		for j in s:
			if j == '1':
				c += 1
		if c <= 3:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	binary_string = input()
	if binary_string.count('1') <= 3 and len(binary_string) > 2:
		print('YES')
	elif len(binary_string) == 2 and binary_string.count('1') == 2:
		print('YES')
	else:
		print('NO')


import math
try:
	t = int(input())
	for r in range(t):
		n = int(input())
		s = input()
		c = 0
		if s == '1' or s == '10':
			print('NO')
		else:
			for i in range(n):
				if s[i] == '1':
					c += 1
			if c <= 3:
				print('YES')
			else:
				print('NO')
except:
	pass


import math
t = int(input())
while t:
	n = int(input())
	s = input()
	k = int(s, 2)
	l = s.count('1')
	if k <= 2:
		print('NO')
	elif l <= 3:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	cnt = s.count('1', 0, n)
	if cnt <= 3:
		if s == '10' or s == '1':
			print('NO')
		else:
			print('YES')
	elif cnt > 3:
		print('NO')
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if s == '1' or s == '10':
		print('NO')
	else:
		cnt1 = s.count('1')
		if cnt1 == 2 or cnt1 == 3 or cnt1 == 1:
			print('YES')
		else:
			print('NO')


n = int(input())
for i in range(n):
	x = int(input())
	y = input()
	v = 0
	if y == '1' or y == '10':
		print('NO')
	else:
		for i in range(x):
			if y[i] == '1':
				v = v + 1
		if v <= 3:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = input()
	v = 0
	if a == '1' or a == '10':
		print('NO')
	else:
		for i in range(n):
			if a[i] == '1':
				v = v + 1
		if v <= 3:
			print('YES')
		else:
			print('NO')


for t in range(int(input())):
	n = int(input())
	a = input()
	if a == '1' or a == '10':
		print('NO')
	else:
		num = 0
		for i in range(n):
			if a[i] == '1':
				num += 1
		if num <= 3:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	l = int(input())
	n = input()
	i = 0
	count = n.count('1')
	if n == '1' or n == '10':
		print('NO')
	elif count <= 3:
		print('YES')
	else:
		print('NO')


def can_be_represented(n, s):
	count_ones = s.count('1')
	if count_ones > 3:
		return 'NO'
	if count_ones == 3:
		if s[-1] == '1':
			return 'YES'
		else:
			return 'NO'
	if count_ones == 2:
		if s[-1] == '0':
			return 'YES'
		else:
			return 'NO'
	if count_ones == 1:
		if s[-2:] == '00':
			return 'YES'
		else:
			return 'NO'
	return 'NO'
for i in range(int(input())):
	l = int(input())
	n = input()
	i = 0
	count = n.count('1')
	if n == '1' or n == '10':
		print('NO')
	elif count <= 3:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	oc = s.count('1')
	if s == '1' or s == '10':
		print('NO')
	elif oc < 4:
		print('YES')
	else:
		print('NO')


cas = int(input())
for i in range(cas):
	n = int(input())
	s = input()
	count = 0
	ans = 'YES'
	if s == '1' or s == '10':
		ans = 'NO'
	else:
		for j in range(n):
			if s[j] == '1':
				count += 1
			if count > 3:
				ans = 'NO'
				break
	print(ans)


for _ in range(int(input())):
	x = int(input())
	y = str(input())
	z = 0
	p = 0
	if y == '1' or y == '10':
		print('NO')
	else:
		b = y.count('1')
		if b <= 3:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	N = int(input())
	S = input()
	sum = 0
	for i in range(0, N):
		if S[i] == '1':
			sum += 1
	if S == '1' or S == '10':
		print('NO')
	elif sum <= 3:
		print('YES')
	else:
		print('NO')


n1 = int(input())
l = []
for i in range(n1):
	h = int(input())
	s = input()
	if s == '1' or s == '10' or s == '01':
		print('NO')
	else:
		c = 0
		for j in s:
			if j == '1':
				c = c + 1
		if c <= 3:
			print('YES')
		else:
			print('NO')


a = int(input())
for i in range(a):
	n = int(input())
	s = int(input())
	if s < 11:
		print('NO')
	elif str(s).count('1') <= 3:
		print('YES')
	else:
		print('NO')


def solve():
	if s.count('1') > 3:
		return 'NO'
	elif int(s, 2) >= 3:
		return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve())


a = int(input())
while a > 0:
	c = int(input())
	b = input()
	j = 0
	for i in range(c):
		j += int(b[i])
	if j >= 4:
		print('NO')
	elif j == 3:
		print('YES')
	elif j == 2:
		print('YES')
	elif j == 1:
		if c >= 3:
			print('YES')
		else:
			print('NO')
	a -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s == '1' or s == '10':
		print('NO')
	else:
		print('YNEOS'[s.count('1') > 3::2])


for _ in range(int(input())):
	n = int(input())
	a = input()
	c = 1
	if a == '1' or a == '10' or a == '0' or (a.count('1') > 3):
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	c2 = 0
	for j in s:
		if j == '1':
			c += 1
		else:
			c2 += 1
	if s == '1' or s == '10':
		print('NO')
	elif c == 3 or c == 2 or c == 1:
		print('YES')
	else:
		print('NO')


def BinaryToDecimal(binary):
	decimal = 0
	for digit in binary:
		decimal = decimal * 2 + int(digit)
	return decimal

def checker(n, ans=1):
	while ans < n:
		ans = ans * 2
	if ans == n:
		return ans
	else:
		return ans // 2
for j in range(int(input())):
	answer = 'NO'
	lenth = int(input())
	k = input()
	k = BinaryToDecimal(k)
	if k < 3:
		print('NO')
	else:
		for i in range(3):
			k = k - checker(k)
			if k == 1 and i <= 1 or k == 0:
				answer = 'YES'
				break
		print(answer)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp1 = lambda : input()
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def solve(num, nums):
	x = int(nums, 2)
	y = nums.count('1')
	if x <= 2:
		return 'NO'
	elif y <= 3:
		return 'YES'
	return 'NO'
tried = int(input())
for _ in range(tried):
	num = inp()
	nums = inp1()
	print(solve(num, nums))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	k = 0
	r = 0
	if s == '1' or s == '10' or s == '01':
		print('NO')
	else:
		while k < len(s):
			if s[k] == '1':
				r = r + 1
			k = k + 1
		if r <= 3:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	t = input()
	k = 0
	e = 0
	if t == '1' or t == '10' or t == '01':
		print('NO')
	else:
		while k < len(t):
			if t[k] == '1':
				e += 1
			k += 1
		if e <= 3:
			print('YES')
		else:
			print('NO')


T = int(input())
for test in range(T):
	N = int(input())
	S = input()
	ones = S.count('1')
	if ones > 3 or (ones < 2 and len(S) < 3):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = 0
	if b == '1' or b == '10':
		print('NO')
	else:
		for i in b:
			if i == '1':
				c += 1
		if c <= 3:
			print('YES')
		else:
			print('NO')


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	Z = S.count('1')
	if Z <= 3 and N > 2:
		print('YES')
	elif N == 2 and S == '11':
		print('YES')
	else:
		print('NO')