A. Gregor and Cryptography

伏欣悦
2023-12-01

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 PP. Gregor wants to find two bases of PP. Formally, Gregor is looking for two integers aa and bb which satisfy both of the following properties.

  • Pmoda=PmodbPmoda=Pmodb, where xmodyxmody denotes the remainder when xx is divided by yy, and
  • 2≤a<b≤P2≤a<b≤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 tt (1≤t≤10001≤t≤1000).

Each subsequent line contains the integer PP (5≤P≤1095≤P≤109), with PP guaranteed to be prime.

Output

Your output should consist of tt lines. Each line should consist of two integers aa and bb (2≤a<b≤P2≤a<b≤P). If there are multiple possible solutions, print any.

Example

input

Copy

2
17
5

output

Copy

3 5
2 4

Note

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

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

解题说明:水题,由于p为质数,找规律能发现2和p-1就能满足条件,余数都为1。

#include <stdio.h>

int main()
{
	int t;
	int n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		printf("2 %d\n", n - 1);
	}
	return 0;
}

 类似资料:

相关阅读

相关文章

相关问答