Chef likes prime numbers. However, there is one thing he loves even more. Of course, it's semi-primes! A semi-prime number is an integer which can be expressed as a product of two distinct primes. For example, $15 = 3 \cdot 5$ is a semi-prime number, but $1$, $9 = 3 \cdot 3$ and $5$ are not.
Chef is wondering how to check if an integer can be expressed as a sum of two (not necessarily distinct) semi-primes. Help Chef with this tough task!

-----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 it is possible to express $N$ as a sum of two semi-primes or "NO" otherwise.

-----Constraints-----
- $1 \le T \le 200$
- $1 \le N \le 200$

-----Example Input-----
3
30
45
62

-----Example Output-----
YES
YES
NO

-----Explanation-----
Example case 1: $N=30$ can be expressed as $15 + 15 = (3 \cdot 5) + (3 \cdot 5)$.
Example case 2: $45$ can be expressed as $35 + 10 = (5 \cdot 7) + (2 \cdot 5)$.
Example case 3: $62$ cannot be expressed as a sum of two semi-primes.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
n = 201
v = [0 for i in range(n + 1)]

def gen():
	for i in range(1, n + 1):
		v[i] = i
	countDivision = [0 for i in range(n + 1)]
	for i in range(n + 1):
		countDivision[i] = 2
	for i in range(2, n + 1, 1):
		if v[i] == i and countDivision[i] == 2:
			for j in range(2 * i, n + 1, i):
				if countDivision[j] > 0:
					v[j] = int(v[j] / i)
					countDivision[j] -= 1
try:
	t = int(sys.stdin.readline())
	for _ in range(t):
		gen()
		x = int(sys.stdin.readline())
		flag = 0
		for i in range(2, x // 2 + 1):
			if v[i] == 1 and v[x - i] == 1:
				flag = 1
		if flag == 1:
			print('YES')
		else:
			print('NO')
except:
	pass


from itertools import combinations_with_replacement
n = 201
s = [0] * n

def sieve(num):
	for i in range(1, num + 1):
		s[i] = i
	cd = [0 for i in range(num + 1)]
	for i in range(num + 1):
		cd[i] = 2
	for i in range(2, num + 1, 1):
		if s[i] == i and cd[i] == 2:
			for j in range(2 * i, num + 1, i):
				if cd[j] > 0:
					s[j] = int(s[j] / i)
					cd[j] -= 1
	res = []
	for i in range(2, num + 1, 1):
		if s[i] == 1 and cd[i] == 0:
			res.append(i)
	return res
t = int(input())
l = [int(input()) for i in range(t)]
count = 0
for i in l:
	a = sieve(i)
	c = list(combinations_with_replacement(a, 2))
	for j in c:
		if j[0] + j[1] == i:
			count += 1
			break
	if count > 0:
		print('YES')
	else:
		print('NO')
	count = 0


def AlmostPrime(n):
	pf = []
	while n % 2 == 0:
		n //= 2
		pf.append(2)
	k = 3
	while k <= n:
		while n % k == 0:
			n //= k
			pf.append(k)
		k += 2
	return len(pf) == 2 and pf[0] != pf[1]

def semi_prime(n):
	for i in range(6, n // 2 + 1):
		if AlmostPrime(i) and AlmostPrime(n - i):
			return 'YES'
	return 'NO'
for _ in range(int(input())):
	print(semi_prime(int(input())))


def seive_array():
	n = 200
	seive = [1] * (n + 1)
	seive[0] = 0
	seive[1] = 0
	i = 2
	while i * i <= n:
		if seive[i] == 1:
			for j in range(i * i, n + 1, i):
				seive[j] = 0
		i += 1
	return seive

def check_semi_prime(x):
	k = 2
	p1 = 0
	p2 = 0
	while k < x:
		if x % k == 0 and seive[k] == 1:
			p1 = k
		if x == p1 * p2 and p1 != p2:
			return 1
		else:
			p2 = p1
			k += 1
	return 0

def given_number(m):
	for i in range(2, m // 2 + 1):
		x = i
		y = m - x
		if check_semi_prime(x) and check_semi_prime(y):
			return 1
t = int(input())
seive = seive_array()
for i in range(t):
	m = int(input())
	if given_number(m):
		print('YES')
	else:
		print('NO')


def primefun(n):
	seive = [1 for i in range(n + 1)]
	i = 2
	while i * i <= n + 1:
		if seive[i] == 1:
			for j in range(i * i, n + 1, i):
				seive[j] = 0
		i = i + 1
	seive[0] = 0
	seive[1] = 0
	return seive

def divide(n, seive):
	for i in range(2, n, 1):
		if n % i == 0:
			if seive[i] == 1 and seive[n // i] == 1:
				if i != n // i:
					return True
count = int(input())
for g in range(count):
	n = int(input())
	flag = 0
	seive = primefun(n)
	for i in range(6, n):
		if i + (n - i) == n:
			k = n - i
			if divide(i, seive) == True and divide(k, seive) == True:
				flag = 1
				print('YES')
				break
	if flag == 0:
		print('NO')


def sievearray():
	n = 200
	sieve = [1 for i in range(n + 1)]
	sieve[0] = 0
	sieve[1] = 0
	i = 2
	while i * i <= n:
		if sieve[i] == 1:
			for j in range(i * i, n + 1, i):
				sieve[j] = 0
		i += 1
	return sieve

def semiprime(n):
	i = 2
	m2 = 0
	m1 = 0
	while i != n:
		if n % i == 0 and sieve[i] == 1:
			m1 = i
		if n == m1 * m2 and m1 != m2:
			return 1
		else:
			m2 = m1
			i += 1
	return 0

def sum_of_two(n):
	for i in range(2, n // 2 + 1):
		p = i
		q = n - i
		if semiprime(p) and semiprime(q):
			return 1
try:
	t = 0
	t = int(input())
	sieve = sievearray()
except Exception:
	pass
l1 = [0 for i in range(0, t)]
for i in range(0, t):
	l1[i] = int(input())
for i in range(0, len(l1)):
	if sum_of_two(l1[i]):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	n = int(input())
	poss = 0
	for i in range(1, n + 1):
		z = i
		y = n - i
		l = []
		op = []
		ok = 2
		while ok * ok <= z:
			if z % ok == 0:
				l.append(ok)
				while z % ok == 0:
					z = z // ok
			ok += 1
		if z != 1:
			l.append(z)
		ok = 2
		while ok * ok <= y:
			if y % ok == 0:
				op.append(ok)
				while y % ok == 0:
					y = y // ok
			ok += 1
		if y != 1:
			op.append(y)
		if len(op) == 2 and op[0] * op[1] == n - i and (len(l) == 2) and (l[0] * l[1] == i):
			poss = 1
			break
	if poss:
		print('YES')
	else:
		print('NO')


try:
	N = 205
	seive = [0] * 205
	i = 2
	while i * 2 < N:
		j = i * 2
		if seive[i] == 0:
			while j < N:
				seive[j] += 1
				j += i
		else:
			while j < N:
				seive[j] = 10
				j += i
		i += 1
	pos = []
	for i in range(N):
		if seive[i] == 2:
			pos.append(i)
	for _ in range(int(input())):
		n = int(input())
		s = 0
		e = len(pos) - 1
		while s <= e:
			if pos[s] + pos[e] > n:
				e -= 1
			elif pos[s] + pos[e] < n:
				s += 1
			else:
				print('YES')
				break
		else:
			print('NO')
except:
	pass


import math

def prime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return -1
	return 1

def perfect(n):
	if math.sqrt(n) == int(math.sqrt(n)):
		return -1
	else:
		return 1

def semiprime(n):
	temp = []
	for i in range(2, n):
		if n % i == 0:
			temp.append(i)
			if len(temp) > 2:
				return -1
	if len(temp) == 1:
		return -1
	if len(temp) == 2:
		if prime(temp[0]) == 1 and prime(temp[1]) == 1:
			return 1
t = int(input())
for _ in range(t):
	n = int(input())
	check = 0
	for i in range(2, n // 2 + 1):
		if semiprime(i) == 1 and semiprime(n - i) == 1:
			check = 1
			break
	if check > 0:
		print('YES')
	else:
		print('NO')


sieve = [True for i in range(201)]
(sieve[0], sieve[1]) = (False, False)
i = 2
p = []
while i <= 200:
	if sieve[i]:
		p.append(i)
		j = i * i
		while j <= 200:
			sieve[j] = False
			j += i
	i += 1
l = len(p)
semi = []
for i in range(l):
	for j in range(i + 1, l):
		if p[i] * p[j] <= 200:
			semi.append(p[i] * p[j])
semi = set(semi)
for _ in range(int(input())):
	n = int(input())
	i = 1
	out = False
	while i <= 100:
		if i in semi and n - i in semi:
			print('YES')
			out = True
			break
		i += 1
	if not out:
		print('NO')


pr = [2]
sv = [0] * 203
for i in range(3, 202, 2):
	if sv[i] == 0:
		pr.append(i)
		for j in range(2 * i, 203, i):
			sv[j] = 1
sp = [0] * (5 * 10 ** 4)
for i in range(len(pr)):
	for j in range(i + 1, len(pr)):
		sp[pr[i] * pr[j]] = 1
for _ in range(int(input())):
	n = int(input())
	an = 'NO'
	for i in range(1, n):
		if sp[i] and sp[n - i]:
			an = 'YES'
			break
	print(an)


p = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
e = [2 * i for i in p]
od = []
for i in range(len(p)):
	for j in range(i + 1, len(p)):
		if p[i] * p[j] <= 200:
			od.append(p[i] * p[j])
		else:
			break
	if j == i + 1:
		break
od.sort()
for i in range(int(input())):
	ans = 0
	n = int(input())
	if n % 2 == 0:
		for i in range(len(od)):
			for j in range(i, len(od)):
				if od[i] + od[j] == n:
					ans = 1
					break
				if od[i] + od[j] > n:
					break
			if ans == 1 or j == i:
				break
		if ans == 0:
			for i in range(len(e)):
				for j in range(i, len(e)):
					if e[i] + e[j] == n:
						ans = 1
						break
					if e[i] + e[j] > n:
						break
				if ans == 1 or j == i:
					break
	else:
		for i in range(len(e)):
			for j in range(len(od)):
				if e[i] + od[j] == n:
					ans = 1
					break
				if e[i] + od[j] > n:
					break
			if ans == 1 or j == 0:
				break
	if ans == 1:
		print('YES')
	else:
		print('NO')


P = [True] * 1001
p = 2
while p * p <= 201:
	for i in range(p * p, 1001, p):
		P[i] = False
	p += 1
sp = [False] * 1010
for i in range(2, 1001):
	j = i + 1
	while i * j <= 1000:
		if P[i] == True and P[j] == True:
			sp[i * j] = True
		j += 1
for t in range(int(input())):
	n = int(input())
	ok = False
	for i in range(2, n):
		if sp[i] == True and sp[n - i] == True:
			ok = True
			break
	if ok == False:
		print('NO')
	else:
		print('YES')


def semiPrime():
	semiprimespro = []
	prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for i in range(6, 201):
		for j in prime:
			if j >= i:
				break
			if i % j == 0:
				if i // j != j and i // j in prime:
					semiprimespro.append(i)
				else:
					break
	return semiprimespro
(semiprimespro, x, w) = (semiPrime(), 0, 0)
for _ in range(int(input())):
	n = int(input())
	for i in semiprimespro:
		if n - i in semiprimespro:
			print('YES')
			w = 0
			break
		else:
			w = 1
	if w == 1:
		print('NO')


t = int(input())
sp = [6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 177, 178, 183, 185, 187, 194]
while t:
	n = int(input())
	f = 1
	for i in range(6, int(n / 2) + 1):
		if i in sp and n - i in sp:
			print('YES')
			f = 0
			break
	if f:
		print('NO')
	t -= 1


try:
	t = int(input())
	for i in range(0, t):
		n = int(input())
		flist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
		glist = []
		hlist = []
		for j in range(0, len(flist)):
			for k in range(j + 1, len(flist)):
				glist.append(flist[j] * flist[k])
		for h in range(0, len(glist)):
			for f in range(h, len(glist)):
				hlist.append(glist[h] + glist[f])
		hlist.sort()
		if n in hlist:
			print('YES')
		else:
			print('NO')
except:
	pass


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	p = []
	for j in range(2, n + 1):
		if j == 2:
			p.append(j)
		else:
			f = 0
			for k in range(2, int(math.sqrt(j) + 1)):
				if j % k == 0:
					f = 1
					break
			if f == 0:
				p.append(j)
	ar = []
	for j in range(0, len(p) - 1):
		for k in range(j + 1, len(p)):
			if p[j] * p[k] < n:
				ar.append(p[j] * p[k])
	f = 0
	for j in range(0, len(ar)):
		if ar[j] * 2 == n or n - ar[j] in ar:
			print('YES')
			f = 1
			break
	if f == 0:
		print('NO')


def w(n):
	(prime, p, a) = ([True for i in range(n + 1)], 2, [])
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			a.append(p)
	return a
(s, e, r) = (w(200), [], [])
for i in range(len(s)):
	for j in range(len(s)):
		if i != j:
			if s[i] * s[j] <= 200 and s[i] * s[j] not in e:
				e.append(s[i] * s[j])
for i in range(len(e)):
	for j in range(len(e)):
		if e[i] + e[j] <= 200 and e[i] + e[j] not in r:
			r.append(e[i] + e[j])
for _ in range(int(input())):
	print('YES') if int(input()) in r else print('NO')


import math

def prime(n):
	c = 0
	if n == 1:
		return 0
	elif n == 2:
		return 1
	else:
		for i in range(2, math.floor(math.sqrt(n)) + 1):
			if n % i == 0:
				c = 1
				break
		if c == 0:
			return 1
		else:
			return 0
for i in range(int(input())):
	k = int(input())
	e = 0
	for i in range(1, k + 1):
		for j in range(i, k + 1):
			if i + j == k:
				(c, d) = (0, 0)
				for m in range(1, i + 1):
					for n in range(m, i + 1):
						if m * n == i and m != n:
							if prime(m) and prime(n):
								c = 1
								break
					if c == 1:
						break
				for o in range(1, j + 1):
					for p in range(o, j + 1):
						if o * p == j and o != p:
							if prime(o) and prime(p):
								d = 1
								break
					if d == 1:
						break
				if c and d:
					e = 1
					break
		if e == 1:
			break
	if e == 1:
		print('YES')
	else:
		print('NO')