#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

As x3JiaYin approaches the Black Mage's hideout, she encounters the notice written above. The Black Wings are a faction led by the Black Mage. They roam Edelstein and when they brought back the Black Mage, they took over the town. x3JiaYin saw that the Black Wings were protecting the hideout. Being a *Master of the Obvious*, x3JiaYin said to no one in particular, "The Black Wings must be protecting the hideout from any foreign intruders. I must get pass their defences."

Looking ahead, x3JiaYin made the following non-obvious observations:

- There are
**T**paths in total that lead to the Black Mage's hideout. - Each path is guarded by at least 1 monster commanded by the Black Wings. For the
**i**path, the number of monsters guarding it is^{th}**N**._{i} - Every monster has a unique identifier which goes from 1 to
**N**(inclusive) for each of the_{i}**T**paths.

Looking at the precarious situation ahead, x3JiaYin decides to unleash her *Legendary Drajon Majesty Dual Bowgun* to defeat the monsters. She used *Ishar's Ring* and managed to kill quite a lot of monsters. However, the monsters with prime identifiers survived. Before she could launch her *Advanced Final Attack* on the remaining monsters, the monsters decided to gang up against her. Two monsters can and will pair up against x3JiaYin if the sum of their identifiers - 1 is prime. For example, Monster 3 and Monster 5 can join forces because 3 + 5 - 1 = 7 is prime. Each monster can join forces with many other monsters. When monsters join forces, they act as one unit and share all their powers. Since each monster has a different power, the combined power of a unit is the number of monsters in it.

x3JiaYin needs your help now! She is horrible at math. For each path, she needs to know the power of the strongest unit of monsters. Otherwise, she might underestimate the danger of the situation, get defeated and fail at life! She orders you to write a program to fulfill this task. And **FAST**.

Since there are **T** paths with different numbers of monsters, your program must be very efficient.

## Input

The first line of input consists of a single integer **T**.

The following **T** lines consists of one integer each, with the **i ^{th}** line containing the integer

**N**.

_{i}## Output

For the **i ^{th}** line, output the danger rating of the most dangerous group for the

**i**path.

^{th}## Limits

0 < **T** ≤ 1000

0 < **N _{i}** ≤ 15000000

## Subtasks

- Subtask 1 (20%):
**T**= 1,**N**≤ 10000_{i} - Subtask 2 (30%):
**T**= 1 ,**N**≤ 15000000_{i} - Subtask 3 (50%): Refer to
*Limits*

## Sample Input 1

1 5

## Sample Output 1

2

## Explanation for Sample Output 1

The largest unit formed will consists of only Monster 3 and Monster 5.

## Sample Input 2

1 7

## Sample Output 2

3

## Explanation for Sample Output 2

The largest unit formed has Monster 3, Monster 5 and Monster 7 in it.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 20 | 7 | 1s | 32MB | Minimum |

2 | 30 | 6 | 1s | 32MB | Minimum |

3 | 50 | 10 | 1s | 32MB | Minimum |

4 | 0 | 2 | 1s | 32MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o warning -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512