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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
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
                #print(i,x-i)
        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

# cook your dish here
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):
            # print(i,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")
      

# cook your dish here
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):
    #print('divide n is',n)
    for i in range(2,n,1):
        if(n%i==0):
            #print('n%i is',i)
            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):
            #print(i,n-i)
            k=n-i
            if divide(i,seive)==True  and  divide(k,seive)==True:
                flag=1
                print('YES')
                break
    if flag==0:
        print('NO')
        
                
           


# cook your dish here
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
                #print(i,x-i)
        if flag==1:
            print("YES")
        else:
            print("NO")
except:
    pass


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")
  



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")
  



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")
  



# cook your dish here
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
        
            


# cook your dish here
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')
    

# cook your dish here
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")
        

# cook your dish here
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
#print(sp[:40])
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")

# cook your dish here
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")

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")

def semiPrime():
    semiprimespro,i = [],6
    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]
    while(i <= 200):
        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;
        i += 1
    return semiprimespro
semiprimespro,x,w = semiPrime(),0,0
for _ in range(int(input())):
    n = int(input())
    for i in semiprimespro:
        a = n - i
        if(a in semiprimespro): print("YES"); w = 0; break
        else: w = 1;
    if(w == 1):
        print("NO")

# cook your dish here
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()
        # print(hlist)
        if (n in hlist):
            print("YES")
        else:
            print("NO")
except:
    pass

# cook your dish here
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")

# cook your dish here
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")