perechi

Se consideră șirul numerelor prime, în ordine crescătoare:

$2$, $3$, $5$, $7$, $11$, $13$, $17$, $\dots$

Pe baza acestuia se construiește un al doilea șir, în care fiecare termen se obține prin concatenarea numărului prim aflat pe o poziție impară cu numărul prim aflat pe poziția pară imediat următoare:

$23$, $57$, $1113$, $\dots$

Astfel, concatenarea lui $2$ cu $3$ produce termenul $23$, concatenarea lui $5$ cu $7$ produce termenul $57$, concatenarea lui $11$ cu $13$ produce termenul $1113$ și așa mai departe.

Din al doilea șir se selectează apoi acei termeni care sunt, la rândul lor, numere prime, obținându-se al treilea șir:

$23$, $3137$, $\dots$

Cerință

Se dau $T$ interogări independente. Pentru fiecare interogare se cunoaște un rang $n$ și se cere determinarea celui de-al $n$-lea termen al celui de-al treilea șir.

Date de intrare

Prima linie a fișierului de intrare perechi.in conține un număr natural $T$, reprezentând numărul de interogări.

Fiecare dintre următoarele $T$ linii conține câte un număr natural $n$, reprezentând rangul termenului căutat în interogarea respectivă.

Date de ieșire

Fișierul de ieșire perechi.out va conține $T$ linii. Pe linia $i$ se va afla răspunsul pentru cea de-a $i$-a interogare, adică termenul de rang $n$ al celui de-al treilea șir corespunzător acelei interogări.

Restricții și precizări

• $1 \leq T \leq 100$
• $1 \leq n \leq 10 \ 000$, pentru fiecare interogare
• În cadrul aceluiași test, diferența dintre cea mai mare și cea mai mică valoare a lui $n$ care apare este cel mult $100$.
• Dimensiunea maximă a unei submisii este de 4KB (4000 de caractere). În timpul concursului aceasta era de 100KB.

Exemplu

perechi.in

2
1
2

perechi.out

23
3137