Chef has the N numbers 1, 2, 3, \dots, N. He wants to give exactly K of these numbers to his friend and keep the rest with him.

He can choose any K numbers such that the [GCD] of any number from Chef's set and any number from his friend's set is equal to 1.

Formally, suppose Chef gives the set of numbers A to his friend and keeps B with himself (where |A| = K and |B| = N - K). Then A and B must satisfy

\gcd(a, b) = 1 \ \ \forall a\in A, b\in B

Chef needs your help in choosing these K numbers. Please find any valid set of K numbers that will satisfy the condition, or tell him that no such set exists.

------ Input Format ------ 

- The first line of 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 two space-separated integers N and K. 

------ Output Format ------ 

For each test case first output a single line containing "YES" (without quotes) if a set of size K satisfying Chef's condition exists; and "NO" if no such set exists. This line is not case-sensitive so "YeS", "nO", etc. are also acceptable. 

Next, if the answer is "YES", print another line containing K distinct space-separated integers from 1 to N denoting the numbers which Chef will give to his friend. The integers can be printed in any order.

If there are multiple solutions, you may print any of them.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N - 1$
- Sum of $N$ over all test cases does not exceed $5*10^{5}$

----- Sample Input 1 ------ 
3
4 1
4 2
6 3

----- Sample Output 1 ------ 
Yes
3
Yes
4 2
No

----- explanation 1 ------ 
Test case $1$: Chef can give $[3]$ to his friend and keep $[1, 2, 4]$ for himself. $3$ is coprime with $1, 2$ and $4$ so the condition is satisfied. Another possible solution is Chef giving $[1]$ to his friend.

Test case $2$: Chef can give $[2, 4]$ and keep $[1, 3]$ (or vice versa). It can be seen that $\gcd(2, 1) = 1$, $\gcd(2, 3) = 1$, $\gcd(4, 1) = 1$, $\gcd(4, 3) = 1$ and so the condition is satisfied.

Test case $3$: There is no set of 3 numbers that can satisfy the given condition.

Difficulty: HARD
Tags: Mathematics

Number theory

Implementation

Starter code:

Solutions:
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')

def prime(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
t = ip()
for _ in range(t):
	(n, k) = inp()
	a = []
	b = []
	pr = prime(n + 1)
	st = n // 2 + 1
	for i in range(2, st):
		a.append(i)
	for i in range(st, n + 1):
		if pr[i]:
			b.append(i)
		else:
			a.append(i)
	sta = list(a)
	stb = list(b)
	b.append(1)
	f = False
	while b:
		if k == len(a):
			f = True
			ans = a
			break
		elif k == len(b):
			f = True
			ans = b
			break
		else:
			a.append(b.pop())
	a = list(sta)
	b = list(stb)
	a.append(1)
	while b:
		if k == len(a):
			f = True
			ans = a
			break
		elif k == len(b):
			f = True
			ans = b
			break
		else:
			a.append(b.pop())
	if f:
		print('Yes')
		ans.sort()
		print(*ans)
	else:
		print('No')


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():

	def find(a):
		x = []
		while a != arr[a]:
			x.append(a)
			a = arr[a]
		for i in x:
			arr[i] = a
		return a

	def union(a, b):
		if size[a] > size[b]:
			arr[b] = a
			size[a] += size[b]
		else:
			arr[a] = b
			size[b] += size[a]
	(n, k) = mp()
	arr = [i for i in range(n + 1)]
	size = [1] * (n + 1)
	i = 2
	while i * 2 <= n:
		if arr[i] == i:
			for j in range(2 * i, n + 1, i):
				(x, y) = (find(i), find(j))
				if x != y:
					union(x, y)
		i += 1
	d = defaultdict(list)
	for i in range(1, n + 1):
		a = find(i)
		d[a].append(i)
	x = list(d.keys())
	x.sort(key=lambda y: len(d[y]))
	ans = []
	N = len(x)
	i = N - 1
	while k > 0 and i >= 0:
		if len(d[x[i]]) <= k:
			ans.append(x[i])
			k -= len(d[x[i]])
		i -= 1
	if k != 0:
		pr('No')
	else:
		pr('Yes')
		for i in ans:
			print(*d[i])
for _ in range(inp()):
	solve()