==Include(page="template/taskheader" task_id="frac")==
 
==Include(page="template/raw")==
 
frac
 
Patratel este mare pasionat de fractii. Intr-o zi el se gandeste sa scrie pe o foaie de hartie, in ordine crescatoare, toate fractiile ireductibile cu numitorul N. Observand insa la timp ca sunt o infinitate de astfel de fractii, el nu se mai oboseste si doreste sa afle doar a P-a fractie din sirul la care s-a gandit.
 
h2. Cerinta
 
Sa se determine numaratorul celei de a P-a fractii din sirul construit dupa regulile de mai sus.
 
h2. Date de Intrare
 
Prima linie a fisierului frac.in contine doua numere intregi N si P, separate prin cate un spatiu, avand semnificatia descrisa in enunt.
 
h2. Date de Iesire
 
Prima linie a fisierului frac.out contine un numar natural care reprezinta numaratorul celei de a P-a fractii din sirul fractiilor ireductibile cu numitorul N.
 
h2. Restrictii si precizari
 
o 1 <= N <= 12 000 000 000 ( 12 miliarde )
o 1 <= P <= 10^14
o Se garanteaza ca rezultatul nu depaseste 2^61
 
h2. Exemplu
 
frac.in frac.out Explicatie
12 5 13 Fractiile sirului sunt: 1/12, 5/12, 7/12, 11/12, 13/12, 17/12, etc. A 5-a fractie din acest sir este 13/12 si are numaratorul 13.
 

==Include(page="template/taskheader" task_id="frac")==
 
Patratel este mare pasionat de fractii. Intr-o zi el se gandeste sa scrie pe o foaie de hartie, in ordine crescatoare, toate fractiile ireductibile cu numitorul $N$. Observand insa la timp ca sunt o infinitate de astfel de fractii, el nu se mai oboseste si doreste sa afle doar a $P$-a fractie din sirul la care s-a gandit.
 
h2. Cerinta
 
Sa se determine numaratorul celei de a $P$-a fractii din sirul construit dupa regulile de mai sus.
 
h2. Date de Intrare
 
Prima linie a fisierului $frac.in$ contine doua numere intregi $N$ si $P$, separate prin cate un spatiu, avand semnificatia descrisa in enunt.
 
h2. Date de Iesire
 
Prima linie a fisierului $frac.out$ contine un numar natural care reprezinta numaratorul celei de a $P$-a fractii din sirul fractiilor ireductibile cu numitorul $N$.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 12 000 000 000$ ( $12$ miliarde )
* $1 ≤ P ≤ 10^14^$
* Se garanteaza ca rezultatul nu depaseste $2^61^$
 
h2. Exemplu
 
table(example). |_. frac.in |_. frac.out |
| 12 5 | 13 |
 
h3. Explicatie
 
Fractiile sirului sunt: $1/12, 5/12, 7/12, 11/12, 13/12, 17/12$, etc. A $5$-a fractie din acest sir este $13/12$ si are numaratorul $13$.
 
==Include(page="template/taskfooter" task_id="frac")==

==Include(page="template/taskfooter" task_id="frac")==

421