sipet

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:
a) 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<p2<p3$. Fiecare grămadă a fost pusă în întregime într-un sipet.
b) 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.
c) Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.

Cerință

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 și precizări

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

Exemplu

sipet.in

3
15 5
10 3
41 11

sipet.out

3 3 0 0 0
2 1 0 1 0
3 1 1 1 0

Explicație

• numărul maxim de sipete este $3$, toate cu câte $3$ monede;
• sau: 2 0 2 0 0 $(1 \cdot 3+1 \cdot 7=2 \cdot 5=10)$; (ambele soluții sunt corecte!)
• numărul maxim de sipete este $3$; $1$ sipet cu $11$, unul cu $13$ și unul cu $17$ monede.