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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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


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


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


from random import randint

def prime(n):
	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))


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)