Problem Description

WARNING!

BLACK WINGS AHEAD!

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:

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 ith line containing the integer Ni.

Output

For the ith line, output the danger rating of the most dangerous group for the ith path.

Limits

0 < T ≤ 1000

0 < Ni ≤ 15000000

Subtasks

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.