Fișierul intrare/ieșire	sipet.in, sipet.out	Sursă	ONI 2015 clasa a 9-a
Autor	Istvan Budai	Adăugată de	Tinca Matei • TincaMatei
Timp de execuție pe test	1.4 sec	Limită de memorie	136072 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Sipet ( clasa a 9-a )

Un arheolog a găsit un sipet interesant. După ce l-a deschis cu grijă, a constatat cu surprindere că sipetul conține bănuți de aur. Uitându-se mai atent a mai găsit ceva: un pergament ascuns într-un compartiment secret al sipetului, cu un text scris într-o limbă antică, pe care, din fericire, arheologul o cunoștea. Din text a reieșit că un grup de negustori foarte bogați a vrut să ascundă în mare secret averea breslei lor, formată din monede de aur, deoarece se prevestea un război cumplit. Negustorii știau că există șanse ca această comoară să fie găsită și confiscată de dușmani, deci s-au sfătuit cum e mai bine să procedeze, cum să ascundă comoara. Arheologul a reușit să deducă din text următoarele:

1. Cele N monede, care formau averea breslei, au fost împărțite în maximum trei feluri de grămezi, formate din p1, p2 și p3 bănuți, p1, p2 și p3 fiind numere prime consecutive, p1
2. Este posibil să existe 0 (zero) grămezi formate din p1 sau p2 sau p3 monede, scopul fiind să se obțină o împărțire în care numărul monedelor rămase nedistribuite să fie minim, iar dacă există mai multe posibilități, se alege aceea pentru care numărul de grămezi este mai mare. Dacă există mai multe astfel de soluții, se consideră corectă oricare dintre ele.
3. Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.

Cerinta

Scrieți un program care determină numărul maxim S de sipete și numărul sipetelor cu p1, p2 respectiv p3 monede, precum și suma donată bisericii.

Date de intrare

Fișierul sipet.in conține, pe prima linie numărul natural T, iar pe următoarele T linii câte două numerele naturale N și p1, despărțite printr-un singur spațiu.

Date de ieșire

Fișierul sipet.out va conține pe primele T linii câte 5 numere naturale, separate prin câte un spațiu: S, x, y, z și r, reprezentând numărul maxim S de sipete, numărul x de sipete cu p1 monede, numărul y de sipete cu p2 monede, respectiv numărul z de sipete cu p3 monede și numărul r de monede donate bisericii, corespunzătoare datelor de intrare de pe linia T+1 a fișierului sipet.in. Dacă există mai multe soluții corecte, este acceptată oricare dintre ele.

Restricții

• 1 ≤ N ≤ 10 000 000
• 2 ≤ p1 < p2 < p3 ≤ N
• 1 ≤ T ≤ 10 – în fișierul de intrare nu vor fi mai mult de 10 perechi de numere N p1

Exemplu