The chef was busy in solving algebra, he found some interesting results, that there are many numbers which can be formed by sum of some numbers which are prime. Chef wrote those numbers in dairy. Cheffina came and saw what the chef was doing. Cheffina immediately closed chef's dairy and for testing chef's memory, she starts asking numbers and chef needs to answer wheater given number N can be formed by the sum of K prime numbers if it yes then print 1 else print 0. 

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, two integers $N, K$.

-----Output:-----
For each test case, output in a single line answer as 1 or 0.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $2 \leq N \leq 10^5$
- $1 \leq K \leq 10^5$

-----Sample Input:-----
2
12 2
11 2

-----Sample Output:-----
1
0

Difficulty: interview

Starter code:

Solutions:
from math import sqrt

def isprime(n):
    if (n % 2 == 0 and n > 2) or n == 1: return 0
    else:
        s = int(sqrt(n)) + 1
        for i in range(3, s, 2):
            if n % i == 0:
                return 0
        return 1

def find(N, K): 
    if (N < 2 * K): 
        return 0
    if (K == 1): 
        return isprime(N) 
    if (K == 2): 
        if (N % 2 == 0): 
            return 1
        return isprime(N - 2); 
    return 1

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    print(find(n, k))




# cook your dish here
def isprime(n):
    i=2 
    while i*i<n:
        if n%i==0:
            return 0 
        i+=1 
    return 1 
def istrue(n,k):
    if n<2*k:
        return 0 
    if k==1:
        return  isprime(n) 
    if k==2: 
        if n%2==0: 
            return 1
        return isprime(n-2) 
    return 1
n=int(input())
for i in range(n):
    n,k=list(map(int,input().split()))
    print(istrue(n,k))
    


#https://www.geeksforgeeks.org/check-number-can-written-sum-k-prime-numbers/
from sys import stdin, stdout
def isprime(x): 
	i = 2
	while(i * i <= x): 
		if (x % i == 0): 
			return 0
		i+=1
	return 1
def isSum(N, K): 
	if (N < 2 * K): 
		return 0
	if (K == 1): 
		return isprime(N) 
	if (K == 2): 
		if (N % 2 == 0): 
			return 1
		return isprime(N - 2); 
	return 1
test = int(stdin.readline())
for _ in range(test):
    n,k = map(int, stdin.readline().split())
    if (isSum(n, k)): 
    	stdout.write("1"+'\n') 
    else: 
    	stdout.write("0"+'\n') 

# cook your dish here
from random  import randint
def prime(n):      #Fermat Little's theorem
    if n<4:
        return n==2 or n==3
    for i in range(5):
        a=randint(2,n-2)
        if pow(a,n-1,n)!=1:
            return False
    return True

def solve(n, k):
    if n<2*k:
        return (0)
    elif k==1:
        if prime(n):
            return (1)
        else:
            return (0) 
    elif k==2:
        if n&1:
            if prime(n-2):
                return (1)
            else:
                return (0)
        else:
            return (1)
    else:
        return (1)
for t_itr in range(int(input())):
    n,k=list(map(int, input().split()))
    print(solve(n,k))


# cook your dish here
import sys
import math
T=int(input())
def is_prime(x):
    for j in range(2,int(math.sqrt(x))+1):
        if x%j==0:
            return 0
    return 1
    
for t in range(T):
    row=list(int(x) for x in input().split())
    N=row[0]
    K=row[1]
    if K==1:
        print(is_prime(N))
    elif K==2 and N>=4:
        if N%2==0:
            print(1)
        else:
            print(0)
    elif K>=3 and N>=2*K:
        print(1)
    else:
        print(0)