Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are playing EVE Online. Initially, you have one dollar, but you have somehow acquired two cheat codes. The first cheat code multiplies the amount of money you own by $10$, while the second one multiplies it by $20$. The cheat codes can be used any number of times.

You want to have exactly $N$ dollars. Now you are wondering: can you achieve that by only using some sequence of cheat codes?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $N$.

------  Output ------
For each test case, print a single line containing the string "Yes" if you can make exactly $N$ dollars or "No" otherwise.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{18}$

----- Sample Input 1 ------ 
4

200

90

1000000000000

1024000000000
----- Sample Output 1 ------ 
Yes

No

Yes

No

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for z in range(t):
	n = int(input())
	i = 20
	l = []
	while n >= i:
		l.append(i)
		i = i * 20
	while n > 10:
		if n in l:
			n = 10
		elif n % 10 == 0:
			n = n / 10
		else:
			n = 8
	if n == 10:
		print('Yes')
	else:
		print('No')


import math
for _ in range(int(input())):
	n = input()
	x = n.rstrip('0')
	m = len(n) - len(x)
	r = math.log(int(x), 2)
	if int(r) == r and r <= m:
		print('Yes')
	else:
		print('No')


import math

def Solve(s):
	zeros = 0
	i = len(s) - 1
	while i >= 0 and s[i] == '0':
		zeros += 1
		i = i - 1
	if i == 0 and s[0] == '1':
		return 'Yes'
	value = int(s[:i + 1])
	x = math.log(value, 2)
	if 2 ** x == value:
		if zeros >= x:
			return 'Yes'
	return 'No'
for _ in range(int(input())):
	n = input()
	print(Solve(n))


T = int(input())
for i in range(0, T):
	a = int(input())
	tim = 0
	mu = 10
	while a % mu == 0:
		mu *= 10
		tim += 1
	mu = mu // 10
	a = a // mu
	mu = 0
	tt = 1
	while a > tt:
		tt *= 2
		mu += 1
	if a == tt:
		if mu <= tim:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	c1 = 0
	c2 = 0
	while n > 1 and n % 10 == 0:
		n //= 10
		c1 += 1
	while n > 1 and n % 2 == 0:
		n //= 2
		c2 += 1
	if c1 >= c2 and n == 1:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	st = input()
	length = len(st)
	j = length - 1
	while j >= 0:
		if st[j] != '0':
			break
		j -= 1
	new = int(st[:j + 1])
	zeros = len(st[j + 1:])
	count = 0
	while True:
		if new == 1 and count <= zeros:
			print('Yes')
			break
		elif new % 2 != 0:
			print('No')
			break
		else:
			new = new // 2
			count += 1


t = int(input())
for i in range(t):
	n = int(input())
	x = 0
	y = 0
	temp = n
	while n % 2 == 0:
		n = n // 2
		x += 1
	while n % 5 == 0:
		n = n // 5
		y += 1
	g = 10 ** (2 * y - x) * 20 ** (x - y)
	if g == temp and x >= 0 and (y >= 0) and (2 * y - x >= 0) and (x - y >= 0):
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	cnt1 = 0
	cnt2 = 0
	while n > 1 and n % 10 == 0:
		cnt1 += 1
		n /= 10
	while n > 1 and n % 2 == 0:
		cnt2 += 1
		n /= 2
	if cnt2 <= cnt1 and n == 1:
		print('Yes')
	else:
		print('No')


import math
t = int(input())
for i in range(t):
	n = int(input())
	n1 = str(n)
	n2 = n1.rstrip('0')
	n2 = int(n2)
	n3 = math.log(n2, 2)
	if n % 10 == 0 and n2 == 1:
		print('Yes')
	elif n3 == int(n3):
		if n3 > n1.count('0') - str(n2).count('0'):
			print('No')
		else:
			print('Yes')
	else:
		print('No')


import math
t = int(input())
for i in range(t):
	a = input()
	n = a.rstrip('0')
	zeroes = len(a) - len(n)
	r = math.log(int(n), 2)
	if int(r) == r and r <= zeroes:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = str(input())
	ans = 'No'
	for i in range(len(n)):
		prob = str(20 ** i)
		Long = len(prob)
		try:
			rem = int(n[Long:])
		except:
			rem = 0
		if prob == n[:Long] and (not rem):
			ans = 'Yes'
			break
	print(ans)


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	two = 0
	five = 0
	while num % 2 == 0:
		num //= 2
		two += 1
	while num % 5 == 0:
		num //= 5
		five += 1
	if num == 1 and five <= two <= 2 * five:
		print('Yes')
	else:
		print('No')


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	while num >= 10:
		ten_log = math.log(num, 10)
		twenty_log = math.log(num, 20)
		if ten_log != int(ten_log) and twenty_log != int(twenty_log):
			num //= 20
		else:
			num = 1
			break
	if num == 1:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n_string = input()
	z_split_index = len(n_string) - 1
	for i in reversed(range(len(n_string))):
		if n_string[i] == '0':
			z_split_index = i
		else:
			break
	is_valid = False
	if len(n_string) > 1:
		zero_count = len(n_string) - z_split_index
		prefix = n_string[:z_split_index]
		is_pow_2 = bin(int(prefix))[2:].count('1') == 1
		req_zero_count = len(bin(int(prefix))[2:]) - 1
		is_zero_count_enough = zero_count >= req_zero_count
		is_valid = is_zero_count_enough and is_pow_2
	print('Yes' if is_valid else 'No')


import math
for _ in range(int(input())):
	n = int(input())
	k = n
	count = 0
	while k > 0:
		if k // 10 == k / 10:
			k = k // 10
			count += 1
		else:
			break
	p = math.log(k, 2)
	if float(p) != math.floor(p):
		print('No')
	elif count < int(p):
		print('No')
	else:
		print('Yes')


import math
t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	while n % 10 == 0:
		count += 1
		n = n // 10
	a = math.log2(n)
	if a != int(a) or int(a) > count:
		print('No')
	else:
		print('Yes')


t = int(input())
for _ in range(t):
	n = int(input())

	def help(n, r):
		if r > n:
			return False
		if n == r:
			return True
		return help(n, r * 10) or help(n, r * 20)
	if help(n, 1):
		print('Yes')
	else:
		print('No')


def check(temp, k):
	if temp == k:
		return True
	if temp * 10 > k and temp * 20 > k:
		return False
	return check(temp * 10, k) or check(temp * 20, k)
for _ in range(int(input())):
	k = int(input())
	temp = 1
	if check(1, k):
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

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

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

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

def si():
	return str(input().strip())
from math import log2
success = 'Yes'
failure = 'No'

def solve(n):
	len_n = len(n)
	nn = n.rstrip('0')
	trailing_zero = len_n - len(nn)
	nn = int(nn)
	l = log2(nn)
	if 2 ** int(l) == nn and trailing_zero >= l:
		return success
	else:
		return failure

def do_codechef():
	for t in rii():
		print(solve(si()))
do_codechef()
exit()


import math
for _ in range(int(input())):
	n = input()
	k = 0
	for i in range(len(n)):
		if n[len(n) - i - 1] != '0':
			break
		else:
			k = k + 1
	n = int(n[:len(n) - k])
	if n & n - 1 == 0:
		l = int(round(math.log(n) / math.log(2), 10))
		if l <= k:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	a = 0
	b = 0
	while n % 10 == 0:
		n = n // 10
		a += 1
	while n % 2 == 0:
		n = n // 2
		b += 1
	print('No' if n != 1 or b > a else 'Yes')


for _ in range(int(input())):
	n = int(input())
	tenc = 0
	twoc = 0
	while n % 10 == 0:
		n = n // 10
		tenc += 1
	while n % 2 == 0:
		n = n // 2
		twoc += 1
	if n != 1 or twoc > tenc:
		print('No')
	else:
		print('Yes')


mod = 1000000007
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	c = 0
	while n % 10 == 0:
		c += 1
		n = n // 10
	d = 0
	while n % 2 == 0:
		d += 1
		n = n // 2
	if n != 1:
		print('No')
	elif c >= d:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	og = n
	temp = n
	c = 0
	b = 0
	while n % 5 == 0:
		n = n / 5
		c += 1
	while temp % 2 == 0:
		temp = temp / 2
		b += 1
	if 2 ** b * 5 ** c == og and c <= b <= 2 * c:
		print('Yes')
	else:
		print('No')


import sys
import os.path
import math
import heapq
from sys import stdin, stdout
from collections import *
from math import gcd, ceil, floor
mod = int(1000000000.0 + 7)
if os.path.exists('Updated prg/Input3d.txt'):
	sys.stdout = open('Updated prg/Output3d.txt', 'w')
	sys.stdin = open('Updated prg/Input3d.txt', 'r')

def sinp():
	return input()

def ninp():
	return int(sinp())

def mapinp():
	return map(int, sinp().split())

def linp():
	return list(mapinp())

def sl():
	return list(sinp())

def prnt(a):
	print(a)

def prntl(a):
	print(a, end=' ')

def prntlist(l1):
	print(*l1)

def power(n):
	return 1 << n
for _ in range(ninp()):
	n = ninp()
	(a, b) = (0, 0)
	while n % 10 == 0:
		n = n // 10
		a = a + 1
	while n % 2 == 0:
		n = n // 2
		b = b + 1
	if n != 1 or a < b:
		prnt('No')
	else:
		prnt('Yes')


T = int(input())
for i in range(T):
	n = int(input())
	(x, y) = (0, 0)
	while n % 10 == 0:
		n //= 10
		x += 1
	while n % 2 == 0:
		n //= 2
		y += 1
	if n == 1 and x >= y:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	(x, y) = (0, 0)
	while n % 10 == 0:
		n //= 10
		x += 1
	while n % 2 == 0:
		n //= 2
		y += 1
	if n == 1 and x >= y:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	while n % 10 == 0:
		c += 1
		n = n // 10
	while c and n % 2 == 0:
		c -= 1
		n = n // 2
	if n == 1:
		print('Yes')
	else:
		print('No')


def cwlk(m, amount):
	if m == amount:
		return 1
	elif m > amount:
		return 0
	else:
		return cwlk(m * 10, amount) or cwlk(m * 20, amount)
t = int(input())
for i in range(t):
	n = int(input())
	if cwlk(1, n) == 1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	(a, b) = (0, 0)
	while n % 10 == 0:
		a += 1
		n /= 10
	while n % 2 == 0:
		b += 1
		n /= 2
	if n != 1:
		print('No')
	else:
		print('Yes' if a >= b else 'No')


from math import *

def panda(s):
	n = len(s)
	cnt = 0
	for i in range(n):
		if s[n - i - 1] != '0':
			x = s[:n - i]
			break
		else:
			cnt += 1
	x = int(x)
	y = log2(x)
	if y % 1 or cnt < y:
		return 'No'
	return 'Yes'
t = int(input())
for _ in range(t):
	s = input()
	print(panda(s))


for _ in range(int(input())):
	n = int(input())
	i = j = 0
	while n % 10 == 0:
		n //= 10
		i += 1
	while n % 2 == 0:
		n //= 2
		j += 1
	if n == 1 and i >= j:
		print('Yes')
	else:
		print('No')


def op(n):
	a = [0] * 10
	if n % 2 != 0 and n % 5 != 0:
		return 'No'
	else:
		d = 2
		while n > 1 and d * d <= n:
			k = 0
			while n % d == 0:
				k += 1
				n = n // d
			if k > 0:
				if d == 2:
					a[2] = k
				elif d == 5:
					a[5] = k
				else:
					return 'No'
			d += 1
		if n > 1 and n != 5:
			return 'No'
		if a[2] < a[5] or a[2] > a[5] * 2:
			return 'No'
		else:
			return 'Yes'
for i in range(int(input())):
	n = int(input())
	print(op(n))


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	idx = n
	for i in s[::-1]:
		if i == '0':
			idx = idx - 1
		else:
			break
	places = len(s) - idx
	g = s[0:idx]
	c = 0
	g = int(g)
	while g % 2 == 0:
		g = g // 2
		c = c + 1
	if c <= places and g == 1:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	falg = 0
	c = 0
	n = int(input())
	while n % 10 == 0:
		n = n / 10
		c += 1
	b = 0
	while n % 2 == 0:
		n /= 2
		b += 1
		if b > c:
			print('No')
			falg = 1
			break
	if falg == 0:
		if n != 1:
			print('No')
		else:
			print('Yes')


for i in range(int(input())):
	a = input()
	p = len(a)
	r = 1
	for i in range(p):
		q = p - 1 - i
		if a[q] != '0':
			r += q
			break
	r = p - r
	a = int(a)
	a = a / 10 ** r
	q = 0
	while a % 2 == 0:
		a = a / 2
		q += 1
	if a == 1 and r >= q:
		print('Yes')
	else:
		print('No')


for T in range(int(input())):
	s = input()
	ind = len(s)
	for i in s[::-1]:
		if i == '0':
			ind -= 1
		else:
			break
	val = len(s) - ind
	a = int(s[0:ind])
	c = 0
	while a % 2 == 0:
		a //= 2
		c += 1
	if c <= val and a == 1:
		print('Yes')
	else:
		print('No')


A = []
for i in range(20):
	for j in range(20):
		A.append(str(2 ** i * 10 ** (i + j)))
T = int(input())
while T:
	N = input()
	if N in A:
		print('Yes')
	else:
		print('No')
	T -= 1


T = int(input())
for _ in range(T):
	N = int(input())
	Count10 = 0
	Count2 = 0
	while N % 10 == 0:
		Count10 += 1
		N = N // 10
	while N % 2 == 0:
		Count2 += 1
		N = N // 2
	if N == 1 and Count2 <= Count10:
		print('Yes')
	else:
		print('No')


t = int(input())
while t:
	t -= 1
	s1 = 0
	s2 = 0
	n = int(input())
	while n % 10 == 0:
		s1 += 1
		n = n / 10
	while n % 2 == 0:
		s2 += 1
		n = n / 2
	if n == 1 and s1 >= s2:
		print('Yes')
	else:
		print('No')


import math

def obtainNum(N):
	C = 0
	D = 0
	while N % 10 == 0:
		N = N / 10
		C += 1
	if math.log(N, 2) - int(math.log(N, 2)) == 0:
		D = int(math.log(N, 2))
		if C >= D:
			print('Yes')
		else:
			print('No')
	else:
		print('No')
try:
	t = int(input())
	for _ in range(t):
		N = int(input())
		obtainNum(N)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	c = 0
	if n % 5 == 0:
		while n % 5 == 0:
			n = n // 5
			c += 1
		if n % 2 == 0:
			k = 0
			while n % 2 == 0:
				n = n // 2
				k += 1
			if c <= k and k <= 2 * c and (n == 1):
				print('Yes')
			else:
				print('No')
		else:
			print('No')
	else:
		print('No')


from math import ceil, floor
t = int(input())
while t:
	t -= 1
	N = int(input())
	m = 0
	while N % 10 == 0:
		m += 1
		N //= 10
	n = 0
	while N % 2 == 0:
		n += 1
		N //= 2
	if N != 1:
		print('No')
		continue
	if m < n:
		print('No')
		continue
	print('Yes')


from sys import stdin, stdout
t = int(stdin.readline())
for i in range(t):
	n = int(input())
	count1 = 0
	count2 = 0
	while 1:
		if n % 10 != 0:
			break
		else:
			n = n // 10
			count1 += 1
	res = 1
	while n >= 2:
		if n % 2 != 0:
			res = 0
			break
		else:
			n = n // 2
			count2 += 1
	if res == 1 and count1 >= count2:
		print('Yes')
	else:
		print('No')


t = int(input())
while t > 0:
	a = input()
	n = len(a)
	z = 0
	for i in range(n - 1, -1, -1):
		if a[i] == '0':
			z += 1
		else:
			break
	s = a[:i + 1]
	s = int(s)
	b = bin(s)[2:]
	if b.count('1') == 1:
		l = len(b) - 1
		if z >= l:
			print('Yes')
		else:
			print('No')
	else:
		print('No')
	t -= 1


T = int(input())
for _ in range(T):
	N = int(input())
	P = N
	k2 = 0
	while P == P // 2 * 2:
		k2 += 1
		P = P // 2
	k5 = 0
	while P == P // 5 * 5:
		k5 += 1
		P = P // 5
	if 2 * k5 >= k2 >= k5 and P == 1:
		print('Yes')
	else:
		print('No')


def solve(n, a, b):
	while n and n % 2 == 0:
		a += 1
		n /= 2
	while n and n % 5 == 0:
		b += 1
		n /= 5
	if n != 1:
		return False
	return b <= a and a <= 2 * b
for _ in range(int(input())):
	print('Yes') if solve(int(input()), 0, 0) else print('No')


def Check_if_endstate_is_1_or_not(num):
	if num == 1:
		return True
	if num % 10 == 0 and num % 20 == 0:
		if Check_if_endstate_is_1_or_not(num / 10) or Check_if_endstate_is_1_or_not(num / 20):
			return True
	if num % 10 == 0:
		return Check_if_endstate_is_1_or_not(num / 10)
	if num % 20 == 0:
		return Check_if_endstate_is_1_or_not(num / 20)
	else:
		return False
t = int(input())
for i in range(t):
	num = int(input())
	if Check_if_endstate_is_1_or_not(num):
		print('Yes')
	else:
		print('No')


import sys
import math
import bisect

def solve(n):
	a = 0
	b = 0
	while n and n % 2 == 0:
		a += 1
		n /= 2
	while n and n % 5 == 0:
		b += 1
		n /= 5
	if n != 1:
		return False
	return b <= a and a <= 2 * b

def main():
	for _ in range(int(input())):
		if solve(int(input())):
			print('Yes')
		else:
			print('No')
main()


def fnc(n):
	if n == 1:
		return True
	elif n % 10 == 0 and n % 20 == 0:
		return fnc(n // 10) or fnc(n // 20)
	elif n % 10 == 0:
		return fnc(n // 10)
	elif n % 20 == 0:
		return fnc(n // 20)
	else:
		return False
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	if fnc(n):
		print('Yes')
	else:
		print('No')


t = int(input())

def recurse(n):
	if n == 1:
		return 1
	if n % 10 == 0 and n % 20 == 0:
		left = recurse(n // 10)
		right = recurse(n // 20)
		return max(left, right)
	elif n % 10 == 0:
		return recurse(n // 10)
	elif n % 20 == 0:
		return recurse(n // 20)
	else:
		return 0
while t:
	n = int(input())
	ans = recurse(n)
	if ans == 0:
		print('No')
	else:
		print('Yes')
	t -= 1


def check(n):
	if n == 1:
		return True
	elif n % 20 == 0:
		return check(int(n / 20)) or check(int(n / 10))
	elif n % 10 == 0:
		return check(int(n / 10))
	else:
		return False
for _ in range(int(input())):
	n = int(input())
	if check(n):
		print('Yes')
	else:
		print('No')


import math
testcase = int(input())
for z in range(testcase):
	S = input()
	S = S[::-1]
	Ending_zeros = ''
	Num_reverse = ''
	for i in range(len(S)):
		if S[i] != '0':
			Num_reverse = S[i:]
			break
		else:
			Ending_zeros = Ending_zeros + '0'
	Num = int(Num_reverse[::-1])
	if str(math.log(Num, 2)).split('.')[1] != '0':
		print('No')
		continue
	elif len(Ending_zeros) < int(math.log(Num, 2)):
		print('No')
		continue
	else:
		print('Yes')


for j in range(int(input())):
	n = int(input())
	(c, d, e) = (0, 0, 0)
	while n != 0:
		if n % 2 == 0:
			n = n // 2
			c += 1
		elif n % 5 == 0:
			n = n // 5
			d += 1
		else:
			if n != 1:
				e = 1
			break
	if e == 1 or c < d or c > 2 * d:
		print('No')
	else:
		print('Yes')


import math
T = int(input())
for i in range(T):
	N = int(input())
	s = 0
	t = 0
	while N >= 1:
		if N % 10 == 0:
			N /= 10
			s += 1
		elif N % 2 == 0:
			N /= 2
			t += 1
		else:
			break
	if N == 1:
		if s >= t:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	flag = 0
	x = 0
	y = 0
	while n != 0:
		if n % 2 == 0:
			n = n // 2
			x += 1
		elif n % 5 == 0:
			y += 1
			n = n // 5
		else:
			if n != 1:
				flag = 1
			break
	if x < y or x > 2 * y or flag == 1:
		print('No')
	else:
		print('Yes')


import math
for _ in range(int(input())):
	n = int(input())
	k = 0
	k1 = 0
	while n >= 1:
		if n % 10 == 0:
			n /= 10
			k += 1
		elif n % 2 == 0:
			n /= 2
			k1 += 1
		else:
			break
	if int(n) == 1:
		if k >= k1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


import math
t = int(input())
while t > 0:
	s = list(input())
	s = s[::-1]
	count = 0
	for i in range(0, len(s)):
		if s[i] == '0':
			count += 1
			continue
		else:
			break
	a = s[i:][::-1]
	a1 = ''.join(map(str, a))
	a1 = int(a1)
	if math.floor(math.log(a1, 2)) == math.ceil(math.log(a1, 2)) and count >= int(math.log(a1, 2)):
		print('Yes')
	else:
		print('No')
	t -= 1


def doit(a):
	a.sort()
	return a[1]
t = int(input())
for x in range(t):
	n = int(input())
	flag = 0
	for m in range(20):
		for k in range(20):
			temp = 10 ** m * 20 ** k
			if n == temp and flag == 0:
				print('Yes')
				flag = 1
	if flag == 0:
		print('No')