Find all pairs (sets) of prime numbers (p,q) such that p*q <= n, where n is given number. 
 
Example 1:
Input: n = 4
Output: 2 2
Explanation: Pair (2, 2) which has both prime 
numbers as well as satisfying the condition 
2*2 <= 4.
Example 2:
Input: n = 8
Output: 2 2 2 3 3 2
Explanation: Pairs(2, 2), (2, 3) and (3, 2)
which has both prime numbers and satisfying
the given condition.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function prime_pairs() which takes n as input parameter and returns a list of pairs in ascending order.
 
Expected Time Complexity: O(n^{2}* sqrt(n))
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 400

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(n^{2}* sqrt(n))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
	def prime_pairs(self, n):
		# Code here

Solutions:
class Solution:

	def prime_pairs(self, n):
		li = []
		li1 = []
		for i in range(2, n + 1):
			li.append(i)
			for j in range(2, i):
				if i % j == 0:
					li.remove(i)
					break
		for k in range(len(li)):
			x = li[k]
			for l in range(len(li)):
				y = li[l]
				if x * y <= n:
					li1.append(x)
					li1.append(y)
		return li1


class Solution:

	def prime_pairs(self, n):
		N = n
		pairs = []
		p = 2
		prime = [True for i in range(N + 1)]
		while p * p <= N:
			if prime[p] == True:
				for i in range(p * p, N + 1, p):
					prime[i] = False
			p += 1
		prime1 = []
		for i in range(2, N + 1):
			if prime[i]:
				prime1.append(i)
		res = []
		for i in range(len(prime1)):
			for j in range(len(prime1)):
				if prime1[i] * prime1[j] <= N:
					res.append(prime1[i])
					res.append(prime1[j])
		return res


class Solution:

	def prime_pairs(self, n):
		res = []
		pn = self.getPrimeNumbers(int(n / 2))
		for i in pn:
			for j in pn:
				if i * j <= n:
					res.append(i)
					res.append(j)
		return res

	def getPrimeNumbers(self, n):
		lst = list(range(2, n + 1))
		p = 2
		while p * p <= n:
			for i in range(p - 2, n - n % p, p):
				if lst[i] != p and lst[i] % p == 0:
					lst[i] = 0
			p = self.getNextPrimeNumber(p + 1, n)
		return list(filter(lambda x: x > 0, lst))

	def getNextPrimeNumber(self, p, n):
		if p == 2:
			return 2
		for i in range(p, n):
			for j in range(2, round(i ** 0.5) + 1):
				if i % j == 0:
					break
				if j == round(i ** 0.5):
					return i
		return -1


import math

class Solution:

	def prime_pairs(self, n):
		l1 = list(range(2, n + 1))
		for i in range(2, int(math.sqrt(n)) + 1):
			if i in l1:
				l1 = list(filter(lambda x: x % i, l1))
				l1.append(i)
		l1.sort()
		l2 = []
		for i in l1:
			for j in l1:
				if i * j <= n:
					l2.append(i)
					l2.append(j)
				if i * j > n:
					break
		return l2


class Solution:

	def prime_pairs(self, n):
		l = []
		for i in range(2, n):
			flag = 0
			for a in range(2, i):
				if i % a == 0:
					flag = 1
			if flag == 0:
				l.append(i)
		c = []
		for i in range(len(l)):
			for j in range(len(l)):
				if l[i] * l[j] <= n:
					c.append(l[i])
					c.append(l[j])
		return c


def isPrime(n):
	if n < 2:
		return False
	if n == 2:
		return True
	for i in range(2, n):
		if n % i == 0:
			return False
	return True

class Solution:

	def prime_pairs(self, n):
		stack = []
		for i in range(n // 2 + 3):
			if isPrime(i):
				stack.append(i)
		result = []
		m = len(stack)
		for i in range(m):
			for j in range(m):
				if stack[i] * stack[j] <= n:
					result.append(stack[i])
					result.append(stack[j])
		return result


def is_prime(n):
	if n > 1:
		for i in range(2, int(n / 2) + 1):
			if n % i == 0:
				return False
		return True
	return False

class Solution:

	def prime_pairs(self, n):
		meet_condition = []
		for i in range(2, n):
			if is_prime(i):
				meet_condition.append(i)
		l = len(meet_condition)
		x = [(i, j) for i in meet_condition for j in meet_condition if i * j <= n]
		return [item for i in x for item in i]


class Solution:

	def prime_pairs(self, n):
		list_prime = [2, 3]
		list_less = []
		for i in range(5, n // 2 + 1):
			for j in range(2, int(i ** 0.5) + 1):
				if i % j == 0:
					break
				elif j == int(i ** 0.5):
					list_prime.append(i)
		for i in list_prime:
			for j in list_prime:
				if i * j <= n:
					list_less.append(i)
					list_less.append(j)
		return list_less


def sieveOfEratosthenes(N):
	isPrime = [1 for i in range(N + 1)]
	(isPrime[0], isPrime[1]) = (0, 0)
	p = 2
	while p * p <= N:
		if isPrime[p] == 1:
			i = p * p
			while i <= N:
				isPrime[i] = 0
				i = i + p
		p = p + 1
	return isPrime

class Solution:

	def prime_pairs(self, n):
		isPrime = sieveOfEratosthenes(n)
		primes = []
		for i in range(2, n + 1):
			if isPrime[i] == 1:
				primes.append(i)
		pairs = []
		for i in range(len(primes)):
			for j in range(len(primes)):
				if primes[i] * primes[j] <= n:
					pairs.append(primes[i])
					pairs.append(primes[j])
		return pairs


class Solution:

	def primes(self, n):
		if n == 2:
			return [2]
		elif n <= 3:
			return [2, 3]
		pl = [True] * 401
		pl[0] = pl[1] = False
		for i in range(2, 21):
			if pl[i]:
				for j in range(i * i, 401, i):
					pl[j] = False
		res = []
		for i in range(2, 401):
			if pl[i] == True:
				res.append(i)
		x = self.bsf(res, n)
		return res[:x + 1]

	def bsf(self, a, k):
		n = len(a)
		(l, h) = (0, n - 1)
		while l <= h:
			m = (l + h) // 2
			if a[m] > k:
				h = m - 1
			else:
				idx = m
				l = m + 1
		return idx

	def prime_pairs(self, n):
		sl = self.primes(n)
		ans = []
		for i in sl:
			for j in sl:
				if i * j <= n:
					ans.append(i)
					ans.append(j)
		return ans


class Solution:

	def prime_pairs(self, n):
		primes = []
		for i in range(2, n + 1):
			for j in range(2, int(i ** 0.5) + 1):
				if i % j == 0:
					break
			else:
				primes.append(i)
		pairs = []
		for k in range(len(primes)):
			for l in range(len(primes)):
				if primes[k] * primes[l] <= n:
					pairs.append(primes[k])
					pairs.append(primes[l])
		return pairs


class Solution:

	def prime_pairs(self, n):
		pairs = []
		for i in range(2, n):
			flagi = 0
			sqrtip = int(i ** (1 / 2)) + 1
			for k in range(2, sqrtip):
				if i % k == 0:
					flagi = 1
					break
			if flagi == 0:
				for j in range(2, n):
					flagj = 0
					sqrtjp = int(j ** (1 / 2)) + 1
					for m in range(2, sqrtjp):
						if j % m == 0:
							flagj = 1
							break
					if flagj == 0:
						if i * j <= n:
							pairs.append(i)
							pairs.append(j)
		return pairs


class Solution:

	def prime_pairs(self, N):
		sieve = []
		for i in range(N + 1):
			sieve.append(0)
		for i in range(2, N + 1):
			if sieve[i] == 0:
				for j in range(i * i, N + 1, i):
					sieve[j] = 1
		primes = []
		for i in range(2, N + 1):
			if sieve[i] == 0:
				primes.append(i)
		sum = []
		for i in range(len(primes)):
			for j in range(len(primes)):
				if primes[i] * primes[j] <= N:
					sum.append(primes[i])
					sum.append(primes[j])
		return sum


class Solution:

	def prime_pairs(self, n):
		arr = [2, 3]
		ans = []
		(a, b) = (0, 0)
		if n > 3:
			for i in range(4, n + 1):
				prime = True
				for j in range(2, int(i ** 0.5) + 1):
					if i % j == 0:
						prime = False
				if prime:
					arr.append(i)
			while arr[a] * arr[b] <= n:
				while arr[a] * arr[b] <= n:
					ans.append(arr[a])
					ans.append(arr[b])
					b += 1
				a += 1
				b = 0
			return ans
		if n <= 3:
			return ''


class Solution:

	def prime_pairs(self, n):
		Prime = []
		Prime_P = []
		for i in range(2, n + 1):
			Prime.append(i)
			for j in range(2, i):
				if i % j == 0:
					Prime.remove(i)
					break
		for i in range(len(Prime)):
			x = Prime[i]
			for j in range(len(Prime)):
				y = Prime[j]
				if x * y <= n:
					Prime_P.append(x)
					Prime_P.append(y)
		return Prime_P


import math
import bisect

class Solution:

	def prime_pairs(self, n):
		if n == 1:
			return []
		a = [True for _ in range(n + 1)]
		primes = []
		for i in range(2, n + 1):
			if a[i]:
				for j in range(i * i, n + 1, i):
					a[j] = False
		for i in range(2, n + 1):
			if a[i]:
				primes.append(i)
		x = primes[0]
		i = 0
		ans = []
		while x <= n / 2:
			y = bisect.bisect(primes, int(n / x))
			for z in range(y):
				ans.append(x)
				ans.append(primes[z])
			i += 1
			x = primes[i]
		return ans


class Solution:

	def prime_pairs(self, n):
		x = []

		def isprime(n):
			if n == 2:
				return True
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		for i in range(2, n // 2 + 1):
			if isprime(i):
				x.append(i)
		ans = []
		for i in range(len(x)):
			first = x[i]
			for j in range(len(x)):
				last = x[j]
				if first * last <= n:
					ans.append(first)
					ans.append(last)
		return ans


class Solution:

	def prime_pairs(self, n):
		prime = [True] * 200
		prime[0] = False
		prime[1] = False
		for i in range(2, 200):
			if prime[i] == True:
				for j in range(i * i, 200, i):
					prime[j] = False
		ans = []
		for i in range(200):
			for j in range(200):
				if prime[i] and prime[j]:
					if i * j <= n:
						ans.append((i, j))
		ans.sort()
		out = []
		for i in ans:
			out.append(i[0])
			out.append(i[1])
		return out


def checkPrime(n):
	if n == 1:
		return False
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

class Solution:

	def prime_pairs(self, n):
		if n < 4:
			return []
		answer = []
		for i in range(2, n // 2 + 1):
			for j in range(2, n // i + 1):
				if checkPrime(i) and checkPrime(j):
					answer.extend([i, j])
		return answer


class Solution:

	def prime_pairs(self, n):
		res = []
		x = []
		for i in range(2, n + 1):
			c = 0
			for j in range(2, i + 1):
				if i % j == 0:
					c += 1
			if c == 1:
				res.append(i)
		for i in res:
			for j in res:
				if i * j <= n:
					x.append(i)
					x.append(j)
		return x


import itertools

class Solution:

	def prime_pairs(self, num):
		prime = [True for i in range(num + 1)]
		p = 2
		while p * p <= num:
			if prime[p] == True:
				for i in range(p * p, num + 1, p):
					prime[i] = False
			p += 1
		primes = [p for p in range(2, num + 1) if prime[p]]
		prime_pairs = [i for i in itertools.product(primes, repeat=2) if i[0] * i[1] <= num]
		prime_pairs.sort()
		return [' '.join(list(map(str, i))) for i in prime_pairs]


class Solution:

	def prime_pairs(self, n):
		l = []
		x = []
		l = []
		for i in range(2, n + 1):
			for j in range(2, i):
				if i % j == 0:
					break
			else:
				l.append(i)
		for i in l:
			for j in l:
				if i * j <= n:
					x.append(i)
					x.append(j)
		return x


class Solution:

	def prime_pairs(self, n):
		prime = []
		for i in range(2, n + 1):
			prime.append(i)
			for j in range(2, i):
				if i % j == 0 and i in prime:
					prime.remove(i)
		prime_pair = []
		for number1 in prime:
			for number2 in prime:
				if number1 * number2 <= n:
					prime_pair.append(number1)
					prime_pair.append(number2)
		return prime_pair


class Solution:

	def prime_pairs(self, n):
		lst = []
		lst1 = []
		for i in range(2, n + 1):
			for j in range(2, i):
				if i % j == 0:
					break
			else:
				lst.append(i)
		for i in lst:
			for j in lst:
				if i * j <= n:
					lst1.append(i)
					lst1.append(j)
		return lst1


import math

class Solution:

	def seive(self, n):
		primes = [True] * n
		primes[0] = primes[1] = False
		for i in range(4, n, 2):
			primes[i] = False
		x = int(math.sqrt(n)) + 1
		for i in range(3, x):
			for j in range(i * i, n, i):
				primes[j] = False
		ans = []
		for i in range(len(primes)):
			if primes[i]:
				ans.append(i)
		return ans

	def prime_pairs(self, n):
		if n <= 3:
			return []
		st = set()
		primes = self.seive(n)
		k = len(primes)
		i = 0
		ans = []
		while i < k:
			j = 0
			while j < k:
				if primes[j] * primes[i] <= n:
					ans.append(primes[i])
					ans.append(primes[j])
				else:
					break
				j += 1
			i += 1
		return ans


import math

class Solution:

	def prime_pairs(self, n):
		arr = []
		for i in range(2, n // 2 + 1):
			if self.cekPrime(i):
				for j in range(2, n // 2 + 1):
					if self.cekPrime(j):
						if i * j <= n:
							arr.append(i)
							arr.append(j)
		return arr

	def cekPrime(self, N):
		number = int(math.sqrt(N)) + 1
		for i in range(2, number):
			if N % i == 0:
				return False
		return True


class Solution:

	def prime_pairs(self, n):
		l = []
		a = []
		for i in range(1, n):
			count = 0
			for j in range(1, i + 1):
				if i % j == 0:
					count += 1
			if count == 2:
				l.append(i)
		for h in l:
			for k in l:
				if h * k <= n:
					a.append(h)
					a.append(k)
		return a


class Solution:

	def prime_pairs(self, n):
		primes = [True] * (n + 1)
		primes[0] = primes[1] = False
		for i in range(2, n):
			if primes[i]:
				for j in range(i + i, n + 1, i):
					primes[j] = False
		li = []
		for i in range(n + 1):
			if primes[i]:
				for j in range(n + 1):
					if primes[j] and i * j <= n:
						li.extend([i, j])
		return li


import math

class Solution:

	def isPrime(self, N):
		if N == 1:
			return 0
		r = int(math.sqrt(N)) + 1
		if r > 1:
			for i in range(2, r):
				if N % i == 0:
					return 0
		return 1

	def prime_pairs(self, n):
		l = []
		ans = []
		for i in range(2, n):
			check_prime = self.isPrime(i)
			if check_prime == 1:
				l.append(i)
		for i in range(len(l)):
			for j in range(len(l)):
				if l[i] * l[j] <= n:
					ans.append(l[i])
					ans.append(l[j])
		return ans


class Solution:

	def prime_pairs(self, n):
		x = []
		y = []
		for num in range(1, n + 1):
			if num > 1:
				for k in range(2, num):
					if num % k == 0:
						break
				else:
					x.append(num)
		for p in x:
			for q in x:
				if p * q <= n:
					y.append(p)
					y.append(q)
		return y
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.prime_pairs(n)
		for i in ans:
			print(i, end=' ')
		print()


import math

class Solution:

	def prime(self, x):
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		return True

	def prime_pairs(self, n):
		ans = []
		for i in range(2, n):
			if self.prime(i):
				ans.append(i)
		res = []
		for i in range(len(ans)):
			for j in range(len(ans)):
				if ans[i] * ans[j] <= n:
					res.append(ans[i])
					res.append(ans[j])
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.prime_pairs(n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def prime_pairs(self, N):
		ans = []

		def isPrime(n):
			if n <= 1:
				return False
			if n == 2 or n == 3:
				return True
			if n % 2 == 0 or n % 3 == 0:
				return False
			for i in range(5, int(n ** 0.5) + 1, 4):
				if n % i == 0 or n % (i + 2) == 0:
					return False
			return True
		for i in range(2, N):
			for j in range(2, N):
				if i * j <= n and isPrime(i) and isPrime(j):
					ans.append(i)
					ans.append(j)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.prime_pairs(n)
		for i in ans:
			print(i, end=' ')
		print()


import math

class Solution:

	def checkPrime(self, n):
		if n == 2:
			return True
		for itr in range(2, math.ceil(math.sqrt(n)) + 1):
			if n % itr == 0:
				return False
		return True

	def prime_pairs(self, n):
		res = []
		for itr in range(2, n):
			for itr2 in range(2, n):
				if itr * itr2 <= n and self.checkPrime(itr) and self.checkPrime(itr2):
					res.append(itr)
					res.append(itr2)
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.prime_pairs(n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def getPrimes(self, n):
		primes = [1] * (n + 1)
		curr = 2
		while curr * curr <= n:
			if primes[curr] == 1:
				for i in range(curr * curr, n + 1, curr):
					primes[i] = 0
			curr += 1
		res = []
		for i in range(2, n + 1):
			if primes[i]:
				res.append(i)
		return res

	def prime_pairs(self, n):
		primes = Solution.getPrimes(self, n)
		res = []
		for valA in primes:
			for valB in primes:
				if valA * valB <= n:
					res.append(valA)
					res.append(valB)
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.prime_pairs(n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def prime_pairs(self, n):
		k = n // 2
		l = [0 for i in range(k + 2)]
		b = []
		for i in range(2, k + 1):
			if l[i] == 0:
				b.append(i)
			j = 2
			c = i * 2
			while c <= k + 1:
				l[c] = 1
				j += 1
				c = i * j
		d = []
		for i in b:
			for j in b:
				if i * j <= n:
					d.append(i)
					d.append(j)
				else:
					break
		return d
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.prime_pairs(n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def prime_pairs(self, n):
		Prime = []
		Prime_P = []
		for i in range(2, n + 1):
			Prime.append(i)
			for j in range(2, i):
				if i % j == 0:
					Prime.remove(i)
					break
		for i in range(len(Prime)):
			x = Prime[i]
			for j in range(len(Prime)):
				y = Prime[j]
				if x * y <= n:
					Prime_P.append(x)
					Prime_P.append(y)
		return Prime_P
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.prime_pairs(n)
		for i in ans:
			print(i, end=' ')
		print()


from math import sqrt

class Solution:

	def prime_pairs(self, n):
		a = []
		b = []
		if n > 1:
			for i in range(2, n + 1):
				for j in range(2, int(sqrt(i)) + 1):
					if i % j == 0:
						break
				else:
					a.append(i)
		for i in a:
			for j in a:
				if i * j <= n:
					b.append(i)
					b.append(j)
		return b


class Solution:

	def isPrime(N):
		i = 2
		while i * i <= N:
			if N % i == 0:
				return 0
			i += 1
		return 1

	def prime_pairs(self, n):
		result = []
		for i in range(2, n + 1):
			if Solution.isPrime(i) == 1:
				for j in range(2, n + 1):
					if Solution.isPrime(j) == 1:
						if i * j <= n:
							result.append(i)
							result.append(j)
		return result


class Solution:

	def prime_pairs(self, n):
		prime = []
		primep = []
		for i in range(2, n + 1):
			prime.append(i)
			for j in range(2, i):
				if i % j == 0:
					prime.remove(i)
					break
		for i in range(len(prime)):
			x = prime[i]
			for j in range(len(prime)):
				y = prime[j]
				if x * y <= n:
					primep.append(x)
					primep.append(y)
		return primep


class Solution:

	def prime_pairs(self, n):
		prime = []
		P = []
		for i in range(2, n + 1):
			prime.append(i)
			for j in range(2, i):
				if i % j == 0:
					prime.remove(i)
					break
		for i in range(len(prime)):
			for j in range(len(prime)):
				if prime[i] * prime[j] <= n:
					P.append(prime[i])
					P.append(prime[j])
		return P


class Solution:

	def prime_pairs(self, n):

		def primes(n):
			i = 2
			l = [0] * (n + 1)
			while i * i <= n:
				if not l[i]:
					for j in range(i * i, n + 1, i):
						l[j] = 1
				i += 1
			k = []
			for i in range(2, n + 1):
				if not l[i]:
					k.append(i)
			return k
		l = primes(n)
		k = []
		for i in range(len(l)):
			for j in range(len(l)):
				if l[i] * l[j] <= n:
					k.append(l[i])
					k.append(l[j])
		return k


class Solution:

	def sieveOfEratosthenes(self, N):
		arr = [False] * (N + 1)
		arr[0] = arr[1] = True
		ans = []
		for i in range(2, N + 1):
			if not arr[i]:
				k = 2
				ans.append(i)
				while k * i <= N:
					arr[k * i] = True
					k += 1
		return ans

	def prime_pairs(self, n):
		ans = self.sieveOfEratosthenes(n)
		fin = []
		for a in ans:
			for b in ans:
				if a * b <= n:
					fin.append(a)
					fin.append(b)
		return fin


class Solution:

	def prime_pairs(self, n):
		import math

		def isprime(n):
			n1 = int(math.sqrt(n))
			for i in range(2, n1 + 1):
				if n % i == 0:
					return 0
			return 1
		l = []
		for i in range(2, n + 1):
			if isprime(i) == 1:
				l.append(i)
		l1 = []
		for i in range(len(l)):
			for j in range(len(l)):
				if l[i] * l[j] <= n:
					l1.append(l[i])
					l1.append(l[j])
		return l1


class Solution:

	def is_prime(self, number):
		if number > 1:
			for num in range(2, int(number ** 0.5) + 1):
				if number % num == 0:
					return False
			return True
		return False

	def prime_pairs(self, n):
		ans = []
		prime_list = []
		for num in range(2, n + 1):
			if self.is_prime(num):
				prime_list.append(num)
		for i in prime_list:
			for j in prime_list:
				if i * j <= n:
					ans.append(i)
					ans.append(j)
		return ans


class Solution:

	def prime_pairs(self, n):
		flag = 0
		lst1 = []
		lst2 = []
		for i in range(2, n + 1):
			flag = 0
			for j in range(2, i // 2 + 1):
				if i % j == 0:
					flag = 1
					break
			if flag == 0:
				lst1.append(i)
		for i in lst1:
			for j in lst1:
				if i * j <= n:
					lst2.append(i)
					lst2.append(j)
		return lst2


class Solution:

	def prime_pairs(self, n):
		p = []
		p1 = []
		for i in range(2, n + 1):
			p.append(i)
			for j in range(2, i):
				if i % j == 0:
					p.remove(i)
					break
		for i in range(len(p)):
			x = p[i]
			for j in range(len(p)):
				y = p[j]
				if x * y <= n:
					p1.append(x)
					p1.append(y)
		return p1


from math import sqrt

class Solution:

	def prime_pairs(self, n):
		l = list()
		c = list()

		def isPrime(N):
			if N % 2 == 0:
				return False
			for i in range(3, int(sqrt(N)) + 2, 2):
				if N % i == 0:
					return False
			return True
		if n == 1:
			return []
		if n == 2:
			return []
		l = [2]
		for i in range(3, n + 1):
			if isPrime(i):
				l.append(i)
		for i in l:
			for j in l:
				if i * j <= n:
					c.append(i)
					c.append(j)
		return c


import math

class Solution:

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

	def prime_pairs(self, n):
		A = []
		for j in range(2, n + 1):
			if self.isPrime(j):
				A.append(j)
		B = []
		for i in range(len(A)):
			for j in range(len(A)):
				if A[i] * A[j] <= n:
					B.append(A[i])
					B.append(A[j])
		return B


import math

class Solution:

	def isprime(self, num):
		if num > 1:
			for n in range(2, num):
				if num % n == 0:
					return False
			return True
		else:
			return False

	def prime_pairs(self, n):
		is_prime = lambda x: False if x <= 1 else len([n for n in range(2, 1 + int(math.sqrt(x))) if x % n == 0]) == 0
		result = []
		for p in range(2, 1 + int(n / 2)):
			if is_prime(p):
				for q in range(2, 1 + int(n / p)):
					if is_prime(q) and p * q <= n:
						result += [p, q]
		return result


class Solution:

	def is_prime(self, n):
		if n == 1:
			return False
		i = 2
		while i * i <= n:
			if n % i == 0:
				return False
			i += 1
		return True

	def prime_numbers(self, num):
		result = []
		for i in range(1, num):
			if self.is_prime(i):
				result.append(i)
		return result

	def prime_pairs(self, n):
		res = []
		nos = self.prime_numbers(n)
		for i in nos:
			for j in nos:
				if i * j <= n:
					res.append([i, j])
		return [i for x in res for i in x]


class Solution:

	def prime_pairs(self, n):
		lst = [2]
		for i in range(3, n // 2 + 1, 2):
			flag = 1
			for j in range(2, int(pow(i, 0.5)) + 1):
				if i % j == 0:
					flag = 0
					break
			if flag != 0:
				lst.append(i)
		lst1 = []
		for i in range(len(lst)):
			for j in range(len(lst)):
				if lst[i] * lst[j] <= n:
					lst1.append(lst[i])
					lst1.append(lst[j])
		return lst1


import math
import itertools

class Solution:

	def prime_pairs(self, n):
		n_limit = n // 2
		prime_lst = []
		for i in range(2, n_limit + 1):
			flag = 0
			for j in range(2, int(math.sqrt(i)) + 1, 1):
				if i % j == 0:
					flag = 1
					break
			if flag == 0:
				prime_lst.append(i)
		length = prime_lst_length = len(prime_lst)
		if length % 2 == 0:
			length = length // 2
		else:
			length = (length + 1) // 2
		result_lst = []
		for i in range(0, length + 1):
			for j in range(i, prime_lst_length):
				if prime_lst[i] * prime_lst[j] <= n:
					result_lst.append((prime_lst[i], prime_lst[j]))
					if not prime_lst[i] == prime_lst[j]:
						result_lst.append((prime_lst[j], prime_lst[i]))
				else:
					break
		result_lst.sort()
		result = list(itertools.chain(*result_lst))
		return result


import math

def checkPrime(i):
	if i == 0 or i == 1:
		return False
	for j in range(2, int(math.sqrt(i)) + 1):
		if i % j == 0:
			return False
	return True

class Solution:

	def prime_pairs(self, n):
		li = []
		for i in range(n):
			if checkPrime(i):
				li.append(i)
		sol = []
		for i in li:
			for j in li:
				if i * j > n:
					break
				sol.append(i)
				sol.append(j)
		return sol


class Solution:

	def prime_pairs(self, n):
		result = []
		primes = [2, 3, 5, 7]
		c = 7
		i = 0
		while c < n / 2 + 1:
			if i % 2 == 0:
				c += 4
			else:
				c += 2
			i += 1
			is_prime = True
			for p in primes[2:]:
				if c % p == 0:
					is_prime = False
					break
			if is_prime:
				primes.append(c)
		for p1 in primes:
			for p2 in primes:
				if p1 * p2 <= n:
					result.append(p1)
					result.append(p2)
		return result


class Solution:

	def prime_pairs(self, n):
		prime = [True for i in range(n + 1)]
		p = 2
		res = []
		while p * p <= n:
			if prime[p]:
				for i in range(p * p, n + 1, p):
					prime[i] = False
			p += 1
		for i in range(2, n + 1):
			if prime[i]:
				res.append(i)
		pair_result = []
		for i in res:
			for j in res:
				if i * j <= n:
					pair_result.append(i)
					pair_result.append(j)
		return pair_result


class Solution:

	def prime_pairs(self, n):
		prime = [True] * (n // 2 + 1)
		p = 2
		while p * p <= n:
			if prime[p]:
				for i in range(p * p, n // 2 + 1, p):
					prime[i] = False
			p += 1
		nums = []
		for i in range(2, n // 2 + 1):
			if prime[i]:
				nums.append(i)
		ans = []
		for p in nums:
			for q in nums:
				if p * q <= n:
					ans.append(p)
					ans.append(q)
		return ans


class Solution:

	def prime_pairs(self, n):
		global prime
		global numbers
		prime = []
		numbers = []
		for i in range(2, n + 1):
			for j in range(2, i):
				if i % j == 0:
					break
			else:
				prime.append(i)
		for p in prime:
			for q in prime:
				if p * q < n + 1:
					numbers.append(p)
					numbers.append(q)
		return numbers


class Solution:

	def isprime(self, K):
		is_prime = 1
		for x in range(2, K):
			if K % x == 0:
				is_prime = 0
		return is_prime

	def prime_pairs(self, N):
		from itertools import permutations, product
		L = range(2, N // 2 + 1)
		prime_list = [x for x in L if self.isprime(x) == 1]
		res = []
		for y in product(prime_list, repeat=2):
			if y[0] * y[1] <= N:
				res.append(str(y[0]))
				res.append(str(y[1]))
		return res


def sieveOfEratosthenes(N):
	ans = []
	prime = []
	for i in range(n + 1):
		prime.append(i)
	prime[0] = 0
	prime[1] = 0
	p = 2
	while p * p <= n:
		if p != 0:
			for i in range(p * 2, n + 1, p):
				prime[i] = 0
		p += 1
	for i in range(len(prime)):
		if prime[i] != 0:
			ans += [prime[i]]
	return ans

class Solution:

	def prime_pairs(self, n):
		ans2 = []
		primes = sieveOfEratosthenes(n)
		for i in range(0, len(primes)):
			for j in range(0, len(primes)):
				if primes[i] * primes[j] <= n:
					ans2 += [primes[i]] + [primes[j]]
		return ans2


class Solution:

	def isPrime(self, x):
		if x == 0 or x == 1:
			return False
		i = 2
		while i * i <= x:
			if x % i == 0:
				return False
			i += 1
		return True

	def prime_pairs(self, n):
		if n == 0 or n == 1:
			return []
		primePairs = []
		for i in range(2, n // 2 + 1):
			for j in range(2, n // 2 + 1):
				if self.isPrime(i) and self.isPrime(j):
					if i * j <= n:
						primePairs.append(i)
						primePairs.append(j)
		return primePairs


class Solution:

	def prime_nums(self, n):
		if n == 1:
			return []
		if n == 0:
			return []
		primes = [True for i in range(n // 2 + 1)]
		p = 2
		while p * p <= n // 2:
			if primes[p] == True:
				for i in range(p * p, n // 2 + 1, p):
					primes[i] = False
			p += 1
		primeNums = [i for i in range(2, n // 2 + 1) if primes[i] == True]
		return primeNums

	def prime_pairs(self, n):
		primeNums = self.prime_nums(n)
		if len(primeNums) == 0:
			return []
		primePairs = []
		for i in range(len(primeNums)):
			for j in range(len(primeNums)):
				if primeNums[i] * primeNums[j] <= n:
					print(primeNums[i], end=' ')
					print(primeNums[j], end=' ')
		return primePairs


class Solution:

	def isPrime(self, n):
		if n == 1:
			return 0
		if n == 2:
			return 1
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return 0
		return 1

	def prime_pairs(self, n):
		arr = [i for i in range(2, n // 2 + 1) if self.isPrime(i)]
		ans = [(arr[i], arr[j]) for i in range(len(arr)) for j in range(len(arr)) if arr[i] * arr[j] <= n]
		return [val for sub in ans for val in sub]


from math import *

class Solution:

	def isprime(self, i):
		sq = int(sqrt(i))
		for j in range(2, sq + 1):
			if i % j == 0:
				return False
		return True

	def prime_pairs(self, n):
		l = []
		for i in range(2, n + 1):
			if self.isprime(i):
				l.append(i)
		l1 = []
		for i in range(len(l)):
			for j in range(len(l)):
				if l[i] * l[j] <= n:
					l1.append(l[i])
					l1.append(l[j])
		return l1


class Solution:

	def isprime(self, n):
		if n == 1:
			return False
		for i in range(2, n):
			if n % i == 0:
				return False
		return True

	def prime_pairs(self, n):
		(a, l) = ([], [])
		for i in range(1, n):
			if self.isprime(i):
				a.append(i)
		for i in range(len(a)):
			for j in range(len(a)):
				if a[i] * a[j] <= n:
					l.append(a[i])
					l.append(a[j])
		return l


def primess(n):
	p = [True] * (n + 1)
	p[0] = False
	p[1] = False
	sev = []
	pr = 2
	while pr * pr <= n:
		if p[pr] == True:
			for j in range(pr * pr, n + 1, pr):
				p[j] = False
		pr += 1
	for i in range(len(p)):
		if p[i] == True:
			sev.append(i)
	return sev

class Solution:

	def prime_pairs(self, n):
		primes = primess(n // 2 + 1)
		result = []
		for i in primes:
			for j in primes:
				if i * j <= n:
					result.append(i)
					result.append(j)
		return result


class Solution:

	def seive(self, n):
		List = []
		prime = [True for i in range(n + 1)]
		prime[0] = prime[1] = False
		p = 2
		while p * p <= n:
			if prime[p]:
				for i in range(p ** 2, n + 1, p):
					prime[i] = False
			p += 1
		for p in range(n + 1):
			if prime[p]:
				List.append(p)
		return List

	def prime_pairs(self, n):
		primes = self.seive(n // 2 + 1)
		result = []
		for i in primes:
			for j in primes:
				if i * j <= n:
					result.append(i)
					result.append(j)
		return result


class Solution:

	def prime_pairs(self, n):

		def isprime(n):
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		l = []
		for i in range(2, n):
			for j in range(2, n // i + 1):
				if i * j <= n and isprime(i) and isprime(j):
					l.extend([i, j])
		return l


import math

class Solution:

	def prime_pairs(self, n):
		primecheck = [True for _ in range(n + 1)]
		checknum = 2
		while checknum * checknum <= n:
			if primecheck[checknum] == True:
				for i in range(checknum * checknum, n + 1, checknum):
					primecheck[i] = False
			checknum += 1
		primelist = []
		for ind in range(2, n + 1):
			if primecheck[ind] == True:
				primelist.append(ind)
		newprimelist = []
		for i in primelist:
			for j in primelist:
				if i * j <= n:
					newprimelist.append(i)
					newprimelist.append(j)
		return newprimelist


class Solution:

	def prime_pairs(self, n):
		Prime = True
		Sum = 0
		prime = []
		for j in range(2, n + 1):
			for i in range(2, j):
				if j % i == 0:
					Prime = False
					break
				else:
					Prime = True
			if Prime == True:
				prime.append(j)
		new_prime = []
		for k in range(0, len(prime)):
			for m in range(0, len(prime)):
				if prime[m] * prime[k] <= n:
					new_prime.append(prime[k])
					new_prime.append(prime[m])
		return new_prime


import math

class Solution:

	def prime_pairs(self, n):
		primeNumberList = list()
		for index in range(2, n + 1):
			if self.isPrime(index) == 1:
				primeNumberList.append(index)
		pairList = list()
		for primeP1 in primeNumberList:
			if primeP1 * primeNumberList[0] > n:
				break
			for primeP2 in primeNumberList:
				if primeP1 * primeP2 <= n:
					pairList.append(primeP1)
					pairList.append(primeP2)
		return pairList

	def isPrime(self, N):
		if N == 1:
			return 0
		factorCount = 1
		for index in range(1, int(math.sqrt(N)) + 1):
			if N % index == 0:
				factorCount += 1
				if factorCount > 2:
					return 0
		return 1


class Solution:

	def __init__(self):
		self.primes = []
		self.pairs = []

	def prime_pairs(self, n):
		if 1 <= n <= 400:
			self.find_primes(n)
			for p1 in self.primes:
				for p2 in self.primes:
					if p1 * p2 <= n:
						self.pairs.append(p1)
						self.pairs.append(p2)
			return self.pairs
		return False

	def find_primes(self, n):
		for i in range(n):
			p = i - 1
			while p:
				if not i % p:
					break
				p -= 1
			if p == 1:
				self.primes.append(i)


class Solution:

	def prime_pairs(self, n):
		lst = []

		def isprime(n):
			if n == 1:
				return False
			elif n == 2 or n == 3:
				return True
			elif n % 2 == 0 or n % 3 == 0:
				return False
			i = 5
			while i * i <= n:
				if n % i == 0 or n % (i + 2) == 0:
					return False
				i = i + 6
			return True
		for i in range(2, n + 1):
			if isprime(i):
				for j in range(2, n + 1):
					if isprime(j) and i * j <= n:
						lst.append(i)
						lst.append(j)
		return lst


class Solution:

	def prime_pairs(self, n):
		arr = []
		if n == 1:
			return []
		for i in range(2, n):
			j = 2
			flag = True
			while j * j <= i:
				if i % j == 0:
					flag = False
					break
				else:
					j += 1
			if flag:
				arr.append(i)
		ans = []
		for i in range(len(arr)):
			for j in range(len(arr)):
				if arr[i] * arr[j] <= n:
					ans.append(arr[i])
					ans.append(arr[j])
		return ans


import math

class Solution:

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

	def prime_pairs(self, n):
		ans = []
		for i in range(2, n // 2 + 1):
			if self.prime(i):
				for j in range(2, n // 2 + 1):
					if self.prime(j) and i * j <= n:
						ans.append(i)
						ans.append(j)
		return ans


class Solution:

	def prime_pairs(self, n):
		lst = []
		for i in range(2, n):
			count = 0
			for j in range(1, i + 1):
				if i % j == 0:
					count = count + 1
			if count == 2:
				lst.append(i)
		lst2 = []
		for i in range(0, len(lst)):
			for j in range(0, len(lst)):
				if lst[i] * lst[j] <= n:
					lst2.append(lst[i])
					lst2.append(lst[j])
		return lst2


class Solution:

	def prime_pairs(self, n):
		results = []
		prime_nums = []
		for num in range(2, n):
			if self.is_prime(num):
				prime_nums.append(num)
		for first_num in prime_nums:
			for second_num in prime_nums:
				if first_num * second_num <= n:
					results.append(first_num)
					results.append(second_num)
		return results

	def is_prime(self, input_number):
		for num in range(2, input_number):
			if input_number % num == 0 and input_number != num:
				return False
		return True


class Solution:

	def prime_pairs(self, n):
		arr = []
		for i in range(0, n + 1):
			arr.append(0)
		i = 2
		while i < n:
			j = 2
			while j * i <= n:
				arr[j * i] = 1
				j += 1
			i += 1
		result = []
		for i in range(2, n + 1):
			if arr[i] == 0:
				result.append(i)
		ans = []
		i = 0
		while i < len(result):
			j = 0
			while j < len(result):
				if result[i] * result[j] <= n:
					ans.append(result[i])
					ans.append(result[j])
				j += 1
			i += 1
		return ans


class Solution:

	def prime_pairs(self, n):
		sieve = [True for _ in range(n + 1)]
		i = 2
		while i * i <= n:
			j = i + i
			while j <= n:
				sieve[j] = False
				j += i
			i += 1
		res = []
		for i in range(2, n + 1):
			for j in range(2, n + 1):
				if sieve[i] and sieve[j] and (i * j <= n):
					res.append(i)
					res.append(j)
		return res


class Solution:

	def prime_pairs(self, n):
		prime = [True] * (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
		primeNum = [i for i in range(2, n + 1) if prime[i] == True]
		ans = [(p, q) for p in primeNum for q in primeNum if p * q <= n]
		ans = [num for i in ans for num in i]
		return ans


import math

class Solution:

	def isPrime(self, n):
		lim = round(math.pow(n, 1 / 2))
		for i in range(2, lim + 1):
			if n % i == 0:
				return 0
		return 1

	def soe(self, n):
		lst = []
		if n == 1:
			return lst
		if n == 2:
			return [2]
		lst.append(2)
		for i in range(3, n + 1):
			if self.isPrime(i) == 1:
				lst.append(i)
		return lst

	def prime_pairs(self, n):
		if n == 1 or n == 2 or n == 3:
			return []
		if n == 4:
			return [2, 2]
		prime_lst = self.soe(math.ceil(n / 2))
		pairs = []
		for i in range(len(prime_lst)):
			for j in range(len(prime_lst)):
				if prime_lst[i] * prime_lst[j] <= n:
					pairs.append(prime_lst[i])
					pairs.append(prime_lst[j])
		return pairs