Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

number theory

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Factorise N+M

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPak Chanek has a prime number$$$^\dagger$$$ $$$n$$$. Find a prime number $$$m$$$ such that $$$n + m$$$ is not prime.

$$$^\dagger$$$ A prime number is a number with exactly $$$2$$$ factors. The first few prime numbers are $$$2,3,5,7,11,13,\ldots$$$. In particular, $$$1$$$ is not a prime number.

Input

Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following lines contain the description of each test case.

The only line of each test case contains a prime number $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

Output

For each test case, output a line containing a prime number $$$m$$$ ($$$2 \leq m \leq 10^5$$$) such that $$$n + m$$$ is not prime. It can be proven that under the constraints of the problem, such $$$m$$$ always exists.

If there are multiple solutions, you can output any of them.

Example

Input

37275619

Output

2 7 47837

Note

In the first test case, $$$m = 2$$$, which is prime, and $$$n + m = 7 + 2 = 9$$$, which is not prime.

In the second test case, $$$m = 7$$$, which is prime, and $$$n + m = 2 + 7 = 9$$$, which is not prime.

In the third test case, $$$m = 47837$$$, which is prime, and $$$n + m = 75619 + 47837 = 123456$$$, which is not prime.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/06/2023 20:15:04 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|