Gregor is learning about RSA cryptography, and although he doesn't understand how RSA works, he is now fascinated with prime numbers and factoring them.

Gregor's favorite prime number is $P$. Gregor wants to find two bases of $P$. Formally, Gregor is looking for two integers $a$ and $b$ which satisfy both of the following properties.

$P mod a = P mod b$, where $x mod y$ denotes the remainder when $x$ is divided by $y$, and

$2 \le a < b \le P$.

Help Gregor find two bases of his favorite prime number!


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

Each subsequent line contains the integer $P$ ($5 \le P \le {10}^9$), with $P$ guaranteed to be prime.


-----Output-----

Your output should consist of $t$ lines. Each line should consist of two integers $a$ and $b$ ($2 \le a < b \le P$). If there are multiple possible solutions, print any.


-----Examples-----

Input
2
17
5
Output
3 5
2 4


-----Note-----

The first query is $P=17$. $a=3$ and $b=5$ are valid bases in this case, because $17 mod 3 = 17 mod 5 = 2$. There are other pairs which work as well.

In the second query, with $P=5$, the only solution is $a=2$ and $b=4$.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	print(2, n - 1)


t = int(input())

def prime(n, i):
	j = int(n / i)
	if i < j and j <= n:
		return True
	else:
		return False
res = []
while t:
	t -= 1
	n = int(input())
	for i in range(2, n):
		if prime(n, i):
			print(i, int(n / i))
			break
		else:
			x = n % i
			j = i + 1
			while j <= n:
				if n % j == x:
					print(i, j)
					break
				else:
					j += 1


def fun(n):
	print(2, n - 1)
T = int(input())
for i in range(T):
	n = int(input())
	fun(n)


n = int(input())
for i in range(n):
	x = int(input())
	print('2', x - 1)


def twoDifferentDividers(n, start):
	i = start if start >= 2 else 2
	while i * i <= n:
		if n % i == 0:
			return (i, n // i)
		i += 1
	return (0, 0)
t = int(input())
anss = []
for _ in range(t):
	P = int(input())
	for q in range(0, P):
		PP = P - q
		candidates = twoDifferentDividers(PP, q)
		if candidates != (0, 0):
			if candidates[0] == candidates[1]:
				anss.append((candidates[0], PP))
			else:
				anss.append(candidates)
			break
for ans in anss:
	print(*ans)


t = int(input())
for _ in range(t):
	p = int(input())
	p -= 1
	print(2, p)


t = int(input())
for a in range(t):
	b = int(input())
	print(2, b - 1)


a = int(input())
j = []
for d in range(a):
	b = input()
	j.append(b)
for f in range(len(j)):
	print(2, int(j[f]) - 1)


for _ in range(int(input())):
	print('2 ' + str(int(input()) - 1))


for i in range(int(input())):
	ab = int(input())
	print(2, ab - 1)


t = int(input())
n = []
for i in range(0, t):
	n.append(int(input()))
for i in range(0, t):
	print(2, n[i] - 1)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(f'{2} {n}')
	else:
		print(f'{2} {n - 1}')


for _ in range(int(input())):
	number = int(input())
	if number % 2 == 0:
		print(2, number)
	else:
		print(2, number - 1)


t = int(input())
for tests in range(t):
	p = int(input())
	a = 2
	for b in range(p, a, -1):
		if p % b == p % a:
			print(a, b)
			break


for _ in range(int(input())):
	P = int(input())
	print(2, '', P - 1)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(f'2 {n - 1}')
main()


t = int(input())
for i in range(0, t):
	a = int(input())
	d = []
	d.append(2)
	d.append(a - 1)
	print(*d, sep=' ')


while True:
	try:
		t = eval(input())
		for i in range(t):
			P = eval(input())
			print(2, P - 1)
	except:
		break


i = int(input())
while i > 0:
	m = int(input())
	k = int((m - 1) / 2)
	if m == 5:
		print(2, '', 4)
	else:
		print(2, '', k)
	i = i - 1


t = int(input())
for i in range(t):
	p = int(input())
	print('2' + ' ' + str(p - 1))


def prime(x):
	if x <= 1:
		return False
	if x <= 3:
		return True
	if x % 2 == 0 or x % 3 == 0:
		return False
	i = 5
	while i * i <= x:
		if x % i == 0 or x % (i + 2) == 0:
			return False
		i += 6
	return True
t = int(input())
for i in range(t):
	p = int(input())
	print(2, p - 1)


def solve(p):
	ans = []
	for i in range(2, p + 1):
		a = p % i
		for j in range(p, i + 1, -1):
			b = p % j
			if a == b:
				ans.append(i)
				ans.append(j)
				return ans
t = int(input())
for _ in range(t):
	p = int(input())
	ans = solve(p)
	print(ans[0], ans[1])


a = int(input())
r = []
for i in range(1, a + 1):
	b = int(input())
	r.append(b - 1)
for v in r:
	print(2, v)


for _ in ' ' * int(input()):
	n = int(input())
	if n > 5:
		print(2, n // 2)
	else:
		print(2, 4)


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlist():
	return input().split(' ')

def yes(t):
	if t:
		return 'YES'
	return 'NO'

def printjoin(l, str=False):
	if str:
		l = [str(i) for i in l]
	return ' '.join(l)

def power_of_two(n):
	b = bin(n)[2:]
	return int(b) == 10 ** (len(b) - 1)

def bit_count(n):
	return bin(n).count('1')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	lcm = x * y // gcd(x, y)
	return lcm

def isint(str):
	try:
		int(str)
		return True
	except ValueError:
		return False

def solve():
	n = int(input())
	if n % 2 == 0:
		return '{} {}'.format(2, n)
	return '{} {}'.format(2, n - 1)
	return ''
t = input()
for tt in range(int(t)):
	print(solve())


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import Decimal
from decimal import *
from collections import defaultdict, deque
import heapq
from decimal import Decimal
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
ABCD = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
months = {1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9: 30, 10: 31, 11: 30, 12: 31}
MOD = 1000000007
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	if n == 5:
		print(2, 4)
	else:
		print(2, n // 2)


t = int(input())
for tc in range(t):
	n = int(input())
	print(2, n - 1)


for _ in range(int(input())):
	n = int(input())
	if 2 == n // 2:
		print(2, 4)
	else:
		print(2, n // 2)


n = int(input())
a = []
for i in range(n):
	v = int(input())
	a.append([2, v - 1])
for i in range(n):
	print(str(a[i][0]) + ' ' + str(a[i][1]))


from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
from collections import Counter
from math import sqrt
import collections
import math
import heapq
import re

def modinv(n, p):
	return pow(n, p - 2, p)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def Divisors(n):
	l = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	return l

def most_frequent(list):
	return max(set(list), key=list.count)

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def Convert(string):
	li = list(string.split(''))
	return li

def SieveOfEratosthenes(n):
	global prime
	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
	f = []
	for p in range(2, n):
		if prime[p]:
			f.append(p)
	return f
prime = []
q = []

def dfs(n, d, v, c):
	global q
	v[n] = 1
	x = d[n]
	q.append(n)
	j = c
	for i in x:
		if i not in v:
			f = dfs(i, d, v, c + 1)
			j = max(j, f)
	return j

def main():
	for _ in range(inin()):
		n = inin()
		if n & 1 == 0:
			print(2, n)
		elif n % 3 == 0:
			print(3, n)
		else:
			print(2, n - 1)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def f():
	p = int(input())
	a = p // 2
	b = a + a
	print(a, b)
t = int(input())
for i in range(t):
	f()


tt = int(input())
for i in range(tt):
	p = int(input())
	if p % 2 != 0:
		p -= 1
	print(2, p)


t = int(input())
for i in range(t):
	n = int(input())
	print('2' + ' ' + str(n - 1))


T = int(input())
res = [[0, 0] for _ in range(T)]
for i in range(T):
	P = int(input())
	res[i][0] = 2
	res[i][1] = P - 1
[print(r[0], r[1]) for r in res]


for t in range(int(input())):
	n = int(input())
	(aa, bb) = (2, 3)
	if n % 2 != 0:
		n -= 1
	print(2, n)


(T,) = map(int, input().split())
for _ in range(T):
	(N,) = map(int, input().split())
	if N % 2:
		print(2, N - 1)
	else:
		print(2, N)


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	print(2, n - 1)


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
from random import randint
for _ in range(nmbr()):
	n = nmbr()
	ans = n // 2
	print(ans, 2 * ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	P = int(input())
	if P == 5:
		print('2 4')
	else:
		first = 2
		second = P - 1
		print(first, second)


N = int(input())
for i in range(N):
	n = int(input())
	if n % 2 != 0:
		n -= 1
	print(2, n)


res = int(input())
for i in range(res):
	a = int(input())
	print(2, a - 1, end=' ')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
for t in range(int(input())):
	n = int(input())
	if n == 5:
		print(2, 4)
		continue
	print(2, (n - 1) // 2)


n = int(input())
for i in range(0, n):
	p = int(input())
	print(2, p - 1)


for _ in range(int(input())):
	s = int(input())
	print(2, s - 1)


n = int(input())
while n:
	print(2, int(input()) - 1)
	n -= 1


n = int(input())
for i in range(n):
	a = int(input())
	v1 = a - 1
	v2 = 2
	print(v2, v1)


for u in range(int(input())):
	n = int(input())
	print((n - 1) // 2, n - 1)


t = int(input())
primes = []
for i in range(t):
	primes.append(int(input()))
for P in primes:
	print(2, P - 1)


for _ in range(int(input())):
	p = int(input())
	print(2, p - 1, sep=' ')


from sys import *
input = stdin.readline
from bisect import *
import math
from collections import *
import operator
from heapq import *
from itertools import *
inf = 10 ** 18
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	n -= 1
	i = 2
	ans = [n]
	while i * i <= n:
		if n % i == 0:
			ans.append(i)
			if i != n // i:
				ans.append(n // i)
		i += 1
	ans.sort()
	print(ans[0], ans[1])


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(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

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return [int(i) for i in input().split()]
t = int(input())
for _ in range(t):
	p = int(input())
	if p & 1:
		print(2, p - 1)
	else:
		print(2, p)


t = int(input())
for _ in range(t):
	p = int(input())
	if p == 5:
		print(2, 4)
	else:
		print(2, p // 2)


for _ in range(int(input())):
	P = int(input())
	if P % 2 == 1:
		print(2, P - 1)
	else:
		print(2, P)


for _ in range(int(input())):
	x = int(input())
	if x <= 5:
		print(2, 4)
	else:
		print(2, x // 2)


for i in range(int(input())):
	print(f'2 {int(input()) - 1}')


def bases(p):
	for i in range(2, p + 1):
		temp = p % i
		tmp1 = p // i
		if tmp1 != i:
			if p % tmp1 == temp:
				return (i, tmp1)
			continue
		else:
			if p % (tmp1 * i) == temp and tmp1 * i <= p:
				return (i, tmp1 * i)
			continue
for _ in range(int(input())):
	p = int(input())
	(a, b) = bases(p)
	print(a, b)


import sys, os
from math import sqrt
from collections import defaultdict
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
T = int(input())
for i in range(T):
	n = int(input())
	if n == 3:
		print()
	md = {}
	for i in range(2, n):
		if n % i in md:
			print(md[n % i], i)
			break
		md[n % i] = i


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def input_list():
	return list(map(int, input().split()))

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
tests = inp()
for _ in range(tests):
	P = inp()
	dicts = dict()
	for i in range(2, P):
		if P % i in dicts:
			print(dicts[P % i], i)
			break
		else:
			dicts[P % i] = i


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 5:
		print(2, 4)
	elif n == 17:
		print(3, 5)
	else:
		n = n - 1
		print(2, n // 2)


for m in range(int(input())):
	n = int(input())
	if n == 2 or n == 3:
		print(1, 2)
	elif n == 5:
		print(2, 4)
	else:
		if (n - 1) // 2 > 2:
			a = 2
			b = (n - 1) // 2
		else:
			a = (n - 1) // 2
			b = 2
		print(a, b)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print((n - 1) // 2, n - 1)
	else:
		print(n // 2, n)


n = int(input())
for i in range(n):
	m = int(input())
	print(2, m - 1)


t = int(input())
num_list = []
for i in range(t):
	num = int(input())
	num_list.append([2, num - 1])
for i in range(t):
	print('{0} {1}'.format(num_list[i][0], num_list[i][1]))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	p = int(input())
	print(2, p - 1)


for _ in range(int(input())):
	p = int(input())
	b = p - 1
	a = b // 2
	print(a, b)


T = int(input())
for _ in range(T):
	N = int(input())
	print(2, N - 1)


n = int(input())
for i in range(n):
	a = int(input())
	print(2, a - a % 2)


def main():
	n = int(input())
	for i in range(n):
		x = int(input())
		a = 2
		b = x - 1
		print(a, b)
main()


def f(a):
	for i in range(2, 100):
		for j in range(2, 100):
			if a % i == a % j and i != j:
				return (i, j)
for _ in range(int(input())):
	a = int(input())
	print(*f(a))


import math
t = int(input())
for _i in range(t):
	p = int(input())
	print(2, p - 1)


tc = int(input())
for _ in range(tc):
	n = int(input())
	if n == 5:
		print('2 4')
	else:
		n -= 1
		b = n // 2
		a = 2
		print(a, b)


def main(p):
	if p % 2 == 0:
		print(2, p)
	else:
		print(2, p - 1)
t = int(input())
for _ in range(t):
	p = int(input())
	main(p)


t = int(input())
i = 0
while i < t:
	p = int(input())
	b = p - 1
	a = b // 2
	print(a, b)
	i += 1


import os
import sys
import math
import collections
import functools
import itertools
import heapq
import bisect
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcde'
MOD = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def INT():
	return int(input())

def STR():
	return input()

def INTS():
	return tuple(map(int, input().split()))

def ARRINT():
	return [int(i) for i in input().split()]

def ARRSTR():
	return [i for i in input().split()]
for _ in range(INT()):
	p = INT()
	print(*[2, p - 1])


import collections as cc
import bisect as bi
import heapq as hp
import math as mt
import itertools as it
import sys
import io, os
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(p,) = I()
	print(2, p - 1)


mod = 1000000007
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
for _ in range(int(input())):
	a = int(input())
	if a == 5:
		print(2, 4)
	else:
		print(2, a // 2)


for s in [*open(0)][1:]:
	print(2, int(s) - 1)


import math
t = int(input())
while t:
	n = int(input())
	m = n - 1
	res = []
	i = 1
	while i <= math.sqrt(m):
		if m % i == 0:
			if m / i == i:
				if i != 1:
					res.append(int(i))
			else:
				if i != 1:
					res.append(int(i))
				if m / i != 1:
					res.append(int(m / i))
		i += 1
		if len(res) >= 2:
			break
	if res[0] < res[1]:
		a = res[0]
		b = res[1]
	else:
		a = res[1]
		b = res[0]
	print(a, b)
	t -= 1


def main():
	tests = int(input())
	while tests > 0:
		n = int(input())
		print(f'{2} {n - 1}')
		tests -= 1
main()


n = int(input())
answer = []
for i in range(0, n):
	p = int(input())
	arr = []
	arr.append(2)
	arr.append(p - 1)
	answer.append(arr)
for k in range(0, n):
	print(answer[k][0], answer[k][1])


import sys
import typing

def rl(proc=None) -> typing.Any:
	if proc is not None:
		return proc(sys.stdin.readline())
	else:
		return sys.stdin.readline().rstrip()

def srl(proc=None) -> typing.List[typing.Any]:
	if proc is not None:
		return list(map(proc, rl().split()))
	else:
		return rl().split()

def main():
	T = rl(int)
	for t in range(1, T + 1):
		P = rl(int)
		print(2, P - 1)
main()


import sys
from collections import Counter
import math
import heapq
num_cases = int(sys.stdin.readline().strip())
for case in range(1, num_cases + 1):
	P = int(sys.stdin.readline().strip())
	signal = 1
	while 1:
		new_P = P - signal
		namuji = 1
		for i in range(2, int(pow(new_P, 0.5)) + 1):
			(mock, namuji) = divmod(new_P, i)
			if namuji == 0:
				print(mock, new_P)
				break
		if namuji == 0:
			break
		else:
			signal += 1


T = int(input())
for t in range(T):
	p = int(input())
	print(2, p - 1)


a = int(input())
while a > 0:
	b = int(input())
	print(int((b - 1) / 2), b - 1)
	a -= 1


for _ in range(int(input())):
	a = int(input())
	print(2, a - a % 2)


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(2, n - 1)


def fun(a):
	i = 2
	rem = []
	while i <= a - 1:
		if a % i in rem:
			k = rem.index(a % i) + 2
			return (k, i)
		else:
			rem.append(a % i)
		i = i + 1
t = int(input())
for j in range(t):
	n = int(input())
	res = fun(n)
	print(res[0], res[1])


n = int(input())
l = []
for _ in range(n):
	l.append(int(input()))
for i in l:
	for j in range(2, i + 1):
		if i // j > 1:
			print(str(j) + ' ' + str(j * (i // j)))
			break


def func(n):
	a = 0
	b = 0
	i = 2
	list = []
	while i < n:
		m = n % i
		if m in list:
			return [list.index(m) + 2, i]
		list.append(m)
		i += 1
t = int(input())
baba = []
for j in range(t):
	baba.append(func(int(input())))
for r in baba:
	print(r[0], r[1])


for i in range(int(input())):
	p = int(input())
	print(2, p - p % 2)


def solve():
	t = int(input())
	for _ in range(t):
		print(f'2 {int(input()) - 1}')
solve()


from math import sqrt, floor
for _ in range(int(input())):
	P = int(input())
	s = floor(sqrt(P))
	if P > 3:
		print(s, P - P % s)
	else:
		print('-1')


n = int(input())
for i in range(n):
	p = int(input())
	print(str(2) + ' ' + str(p - 1))


t = int(input())
for i in range(0, t):
	n = int(input())
	if n == 5:
		print(str(2) + ' ' + str(4))
	else:
		m = (n - 1) // 2
		print(str(2) + ' ' + str(m))


k = int(input())
while k > 0:
	n = int(input())
	if n == 5:
		print('2 4')
	elif n % 2 == 0:
		rest = int(n / 2)
		print('2 ' + str(rest))
	else:
		n -= 1
		rest = int(n / 2)
		print('2 ' + str(rest))
	k = k - 1


def main():
	n = int(input())
	print(2, n - 1)
for i in range(int(input())):
	main()


t = int(input())
res = []
for i in range(t):
	p = int(input())
	res.append([2, p - 1])
for el in res:
	print(el[0], el[1])


import sys, math, bisect
sys.setrecursionlimit(10 ** 4)
from random import randint
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	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
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def isPrime(n, k=5):
	if n < 2:
		return True
	for i in range(0, k):
		a = randint(1, n - 1)
		if pow(a, n - 1, n) != 1:
			return False
	return True
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
import string
for _ in range(int(input())):
	n = int(input())
	print(2, (n - 1) // 2 * 2)


t = int(input())
for i in range(t):
	P = int(input())
	print('2 {}'.format(P - 1))


t = int(input())
for o in range(t):
	n = int(input())
	mods = []
	divs = []
	for i in range(2, n + 1):
		if n % i in mods:
			print(divs[mods.index(n % i)], i)
			break
		mods += [n % i]
		divs += [i]


l = int(input())
for i in range(l):
	p = int(input())
	p = p - 1
	print(2, p)


t = int(input())
for _ in range(t):
	P = int(input())
	if P % 2 != 0:
		P -= 1
	print(2, P)


t = int(input())
for i in range(t):
	p = int(input())
	done = False
	for a in range(2, p):
		for b in range(p, a + 1, -1):
			if p % a == p % b:
				print(a, b)
				done = True
				break
		if done:
			break


t = int(input())
for _ in range(t):
	n = int(input())
	print('2 ', end='')
	print(n - 1)


test = int(input())
for i in range(test):
	p = int(input())
	print(2, p - 1)


t = int(input())
for _ in range(t):
	p = int(input())
	if p % 2 == 0:
		a = 2
		b = p
	else:
		a = 2
		b = p - 1
	print(a, b)


t = int(input())
ls = []
for i in range(0, t):
	ls.append(int(input()))
for i in ls:
	ls1 = [0, 0]
	non_prime = i - 1
	ls1[0] = 2
	if non_prime / 2 == 2:
		ls1[1] = int(2 * (non_prime / 2))
	else:
		ls1[1] = int(non_prime / 2)
	for k in ls1:
		print(k, end=' ')
	print()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	print((n - 1) // 2, n - 1)


for k in range(int(input())):
	n = int(input())
	print(2, n - 1)


for i in range(0, int(input())):
	p = int(input())
	a = (p - 1) // 2
	b = p - 1
	print(a, b)


from math import ceil
for _ in range(int(input())):
	p = int(input())
	x = ceil(p / 2) - 1
	print(*sorted([p - 1, p - x - 1]))


t = int(input())
for case in range(t):
	p = int(input())
	print(2, p - 1)


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
inp = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, input().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, input().split())
lis = lambda : list(mis())
stinput = lambda : stdin.readline()[:-1]
stinp = lambda : int(stinput())
stmi = lambda : map(int, stdin.readline().split())
stli = lambda : list(stmi())
stmi1 = lambda : map(int1, stdin.readline().split())
stli1 = lambda : list(stmi1())
stmis = lambda : stdin.readline()[:-1]
pr = print
from collections import defaultdict
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
t = inp()
for _ in range(t):
	p = stinp()
	print(2, p - 1)


import sys
from os import path
import bisect
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output1.txt', 'w')
from heapq import heappop, heappush, heapify
from math import ceil
from collections import defaultdict
maxi = sys.maxsize
mini = -maxi
for _ in range(int(input())):
	n = int(input())
	if n % 2:
		print(2, n - 1)
	else:
		print(2, n)


import sys
inp = [int(x[:-1]) for x in sys.stdin.readlines()]
for i in inp[1:]:
	print('2' + ' ' + str(i - 1))


for _ in range(int(input())):
	p = int(input())
	print(f'{2} {p - 1}')


n = int(input())
while n != 0:
	n -= 1
	m = int(input())
	if m % 2 == 0:
		print(2, int(m / 2))
		print(end=' ')
	else:
		print(2, m - 1)
		print(end=' ')


t = int(input())
while t:
	n = int(input()) - 1
	m = n // 2
	if m == 2:
		m *= 2
	print(2, m)
	t -= 1


n = int(input())
for i in range(n):
	t = int(input())
	arr = []
	if t % 2 == 1:
		print('2', t - 1)
	elif t % 2 == 0:
		print('2', '4')


for s in range(int(input())):
	a = int(input())
	print(2, int(a) - 1)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		n = int(input())
		if n == 5:
			print(2, 4)
			continue
		n -= 1
		print(2, n // 2)
	return
main()


for y in range(int(input())):
	n = int(input())
	if n == 5:
		print(2, 4)
	else:
		print(2, (n - 1) // 2)


import os
import sys
from math import ceil, floor, sqrt, gcd, factorial
from io import BytesIO, IOBase
from collections import Counter
BUFSIZE = 8192

def main():
	for _ in range(int(input())):
		n = int(input())
		print(2, n - 1)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for i in range(int(input())):
	a = int(input())
	print(2, a - 1)


for i in range(int(input())):
	n = int(input())
	n -= 1
	print('%d %d' % (2, n))


number = int(input())
for i in range(number):
	chislo = int(input())
	if chislo % 2 == 1:
		print(2, chislo - 1)
	elif chislo % 3 == 1:
		print(3, chislo - 1)
	elif chislo % 3 == 2:
		print(3, chislo - 2)


for i in range(int(input())):
	a = int(input())
	if a % 2 == 0:
		print(2, a)
	else:
		print(2, a - 1)


from sys import stdin, stdout
from os import path
rd = lambda : stdin.readline().strip()
wr = stdout.write
if path.exists('input.txt'):
	stdin = open('input.txt', 'r')
import time, math
for _ in range(int(rd())):
	x = int(rd())
	if x // 2 == 2:
		print(2, 4)
	else:
		print(2, x // 2)


import sys

def main():
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		n -= 1
		print(2, n)
main()


n = int(input(''))
l1 = [0]
l1 = l1 * n
for i in range(1, n + 1):
	l1[i - 1] = int(input(''))
for i in range(1, n + 1):
	print(2, l1[i - 1] - 1)


num = int(input())
var1 = 0
var2 = 1
for x in range(num):
	test = int(input())
	a = test // 2
	b = a * 2
	print(a, b)


def main():
	t = int(input())
	for i in range(t):
		p = int(input())
		if p % 2 == 0:
			print(3, p - p % 3)
		else:
			print(2, p - p % 2)
main()


cases = int(input())
for case in range(cases):
	P = int(input())
	print(2, P - 1)


t = int(input())
for o in range(t):
	p = int(input())
	print(2, p - 1)


t = int(input())
for i in range(t):
	p = int(input())
	r = p % 2
	if r == 0:
		print(f'{2} {p}')
	else:
		print(f'{2} {p - 1}')


from sys import *

def inputs():
	return stdin.readline()
for _ in range(int(inputs())):
	n = int(inputs())
	if n == 5:
		print(2, 4)
		continue
	print(2, n // 2)


n = int(input())
mas = []
g = []
for i in range(n):
	g = (2, int(input()) - 1)
	mas.append(g)
for i in range(len(mas)):
	print(*mas[i])


t = int(input())
for j in range(t):
	p = int(input())
	if p == 5:
		a = 2
		b = 4
	else:
		a1 = p // 2
		b1 = p // a1
		a = min(a1, b1)
		b = max(a1, b1)
	print(a, b)


T = int(input())
while T > 0:
	T -= 1
	a = int(input())
	x = a - 1
	ans1 = 2
	print(ans1, ' ', x)


t = int(input())
a = []
for i in range(t):
	a.append(int(input()))
h = 1
d = 1
for i in range(t):
	f = [a[i] % 2]
	for j in range(3, a[i]):
		c = a[i] % j
		for u in range(j - 2):
			if f[u] == c:
				v = str(u + 2) + ' ' + str(j)
				print(v)
				h = 0
				break
		f.append(c)
		if h == 0:
			break
	h = 1


import sys
input = sys.stdin.readline
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left, bisect
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(2, n - 1)
	else:
		print(2, n // 2)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	if n & 1:
		print(n // 2, n - 1)
	else:
		print(n // 2 - 1, n - 1)


t = int(input())
for _ in range(t):
	P = int(input())
	dic = {}
	for i in range(2, P + 1):
		rem = P % i
		brk = False
		try:
			if dic[rem]:
				print(dic[rem], i)
				brk = True
		except KeyError:
			dic[rem] = i
		if brk:
			break


t = int(input())
for i in range(t):
	P = int(input())
	if P % 2 == 0:
		print(2, P)
	else:
		print(2, P - 1)