Problema in C++



O secvență de numere întregi poate fi reprezentată grafic foarte ușor, dacă adăugăm pe grafic toate punctele de coordonate (i, ai). În acest caz, i reprezintă o poziție a unui element din secvență, iar ai reprezintă elementul de pe poziția i din secvență.



De exemplu, putem reprezenta grafic secvența (1, 4, 3, 4) în felul următor: (poza in fisierul atasat)



În această problemă vei folosi o secvență de numere întregi descoperită în anul 2001 și numită Secvența EKG, datorită asemănării graficului ei cu o electrocardiogramă.



Secvența EKG e definită în felul următor:



a[1] = 1

a[2] = 2

a[n] = cel mai mic număr x care nu apare pe pozițiile anterioare în secvență, iar cmmdc(x, a[n - 1]) != 1, unde cmmdc(a, b) e cel mai mare divizor comun al lui a și b

Astfel, secvența începe cu 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15...



Cerință

Află elementul de pe poziția n din secvența EKG.



Date de intrare

Pe prima linie se află un singur număr natural, n.



Date de ieșire

Se va afișa un singur număr natural, reprezentând elementul de pe poziția n din secvența EKG.



Restricții

1 ≤ n ≤ 1 000