Vrăjitoarea cea bună are un cufăr în care este închisă piatra magică de către piticii lăzii cu ajutorul unui cifru digital. Piticii i-au dat vrăjitoarei o cutie în care sunt n cartonaşe. Pe fiecare cartonaş este scris un număr natural pe care vrăjitoarea îl va folosi să deschidă lada. Valorile scrise pe cartonaşe sunt distincte între ele.

Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaş din cutie şi apoi determină valoarea magică asociată numărului natural scris pe cartonaş. Pentru fiecare cartonaş valoarea magică este dată de al k-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obţinute pentru cele n cartonaşe şi apoi să introducă în ordine cifrele valorii obţinute, pentru a descuia lada.

Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaş din cutie şi apoi determină valoarea magică asociată numărului natural scris pe cartonaş. Pentru fiecare cartonaş valoarea magică este dată de al $k$-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obţinute pentru cele n cartonaşe şi apoi să introducă în ordine cifrele valorii obţinute, pentru a descuia lada.

h2. Cerinţă

h2. Date de intrare

Fişierul de intrare este cufar.in.

Fişierul de intrare este $cufar.in$.

Pe prima linie a fişierului de intrare se găsesc o valoare p care poate fi doar 1 sau 2 şi numărul n de cartonaşe despărţite prin câte un spaţiu.

Dacă p este 1 pe linia a doua a fişierului de intrare se găsesc două valori reprezentând numărul de pe cartonaşul dat şi valoarea k, separate printr-un spaţiu, cu semnificaţia de mai sus.

Dacă $p$ este $1$ pe linia a doua a fişierului de intrare se găsesc două valori reprezentând numărul de pe cartonaşul dat şi valoarea $k$, separate printr-un spaţiu, cu semnificaţia de mai sus.

Dacă p este 2 pe următoarele n linii ale fişierului de intrare se găsesc câte două valori, separate prin câte un spaţiu, reprezentând numărul de pe cartonaş şi valoarea lui k pentru fiecare din cele n cartonaşe.

Dacă $p$ este $2$ pe următoarele $n$ linii ale fişierului de intrare se găsesc câte două valori, separate prin câte un spaţiu, reprezentând numărul de pe cartonaş şi valoarea lui $k$ pentru fiecare din cele $n$ cartonaşe.

h2. Date de ieşire

Fişierul de ieşire este cufar.out.

Fişierul de ieşire este $cufar.out$.

Dacă valoarea lui p este 1, atunci se va rezolva doar cerinţa 1 şi fişierul de ieşire va conţine pe prima
linie valoarea magică asociată cartonaşului dat.

Dacă valoarea lui $p$ este $1$, atunci se va rezolva doar cerinţa $1$ şi fişierul de ieşire va conţine pe prima linie valoarea magică asociată cartonaşului dat.

Dacă valoarea lui p este 2, atunci se va rezolva doar cerinţa 2 şi fişierul de ieşire va conţine pe prima
linie cifrul necesar deschiderii cufărului.

Dacă valoarea lui $p$ este $2$, atunci se va rezolva doar cerinţa $2$ şi fişierul de ieşire va conţine pe prima linie cifrul necesar deschiderii cufărului.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n < 1 000 000$
* $2 ≤ valoarea înscrisă pe un cartonaş ≤ 1 000 000$
* Se garantează că pentru fiecare pereche $(număr, k)$, număr are cel puţin $k$ divizori primi.
* Pentru rezolvarea corectă a cerinţei $1$ se acordă $18$ puncte
* Pentru rezolvarea corectă a cerinţei $2$ se acordă $72$ de puncte
* Pentru rezultate corecte la cerinţa a doua respectând restricţiile problemei şi $n ≤ 1000$ se acordă $18$ puncte
* Pentru rezultate corecte la cerinţa a doua respectând restricţiile problemei şi $n ≤ 500 000$ se acordă $43$ de puncte
* Conform regulamentului OJI, se vor acorda $10$ puncte din oficiu (cand adaugam testele facem specificatii in paranteza cum se obtin).

h2. Exemplu