Pracsiu Dan (dnprx) Spunem că un număr natural este aproape prim dacă el poate fi scris ca produs de două numere prime. De exemplu 6 și 25 sunt aproape prime pentru că 6 = 2 * 3, iar 25 = 5 * 5. Considerăm șirul crescător al numerelor naturale aproape prime: 4, 6, 9, 10, 14, 15, 21, … Acestora li se asociază câte un număr de ordine, numerotarea începând cu 1. Deci 4 este primul număr aproape prim, 6 este al doilea număr, 9 este al treilea etc.
Cerința
Dat un număr natural N, să se determine al N-lea număr aproape prim.
Date de intrare
Programul citește de la tastatură numărul N.
Date de ieșire
Programul va afișa pe ecran un singur număr natural, reprezentând al N-lea număr aproape prim.
Restricții și precizări
1 ≤ N ≤ 23.378
Exemplul 1:
Intrare
4
Ieșire
10
Exemplul 2:
Intrare
300
Ieșire
1003