ciocolata

Pe o masă se găsesc batoane de ciocolată. Fiecare baton de ciocolată este format din cel puțin 2 și cel mult 16 tablete.

Două fete – A și B, joacă un joc în care fiecare mută alternativ, A efectuând prima mutare. Fata aflată la mutare trebuie să aleagă unul dintre batoanele rămase pe masă și să folosească una dintre următoarele variante:
a. Dacă batonul are două tablete, îl rupe în două tablete pe care le mănâncă.
b. Dacă batonul are cel puțin trei tablete rupe o tabletă dintr-un capăt, o mănâncă și lasă batonul rămas pe masă.
c. Dacă batonul are cel puțin patru tablete, îl rupe în două batoane de cel puțin două tablete și lasă cele două batoane pe masă fără să mănânce nimic.

În tabelul de mai jos sunt explicate mutările care pot fi aplicate pentru batoane de 2, 3, 4 și 5tablete, în coloana din dreapta fiind înnegrite tabletele care trebuie mâncate la mutarea corespunzătoare.

Jocul se termină când se nu mai este ciocolată pe masă. Scopul jocului este pentru fiecare fată să mănânce cât mai puțină ciocolată (fetele nu vor să se îngrașe). Se știe că cele două concurente sunt extrem de inteligente deci fiecare joacă optim.

Cerință

Pentru t configurații ale jocului în care se cunosc numerele de batoane de fiecare tip să se stabilească numărul de tablete mâncate de fiecare fată la finalul jocului.

Date de intrare

Fișierului de intrare ciocolata.in conține pe prima linie un număr natural t – reprezentând numărul de configurații ale jocului la care trebuie să se găsească raspunsul. Următoarele t linii descriu câte o configurație a unui joc. Fiecare dintre aceste linii conțin câte 15 numere naturale - separate prin câte un spațiu - $c_2, c_3, c_4, ..., c_{16}$ reprezentând numărul de batoane de 2, 3, 4, ..., 16 tablete aflate pe masă la începutul jocului.

Date de ieșire

Fișierului de ieșire ciocolata.out se va conține t linii descriind rezultatul celor t configurații din fișierul de intrare. Pe fiecare dintre aceste linii se vor scrie câte două numere naturale x și y – separate prin spațiu, x - reprezentând numarul de tablete mâncate de A iar y - numărul de tablete mâncate de B la jocului corespunzător din fișierul de intrare.

Restricții

• 1 ≤ t ≤ 30 002
• Pentru 30% din teste, pentru fiecare din cele t configuratii vor fi doar batoane de dimensiune 2, 3, 4, sau 5.
• Pentru fiecare dintre cele t configurații numărul de batoane de fiecare tip este număr natural și nu depașește 30 002.

Exemplu

ciocolata.in

1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0	

ciocolata.out

3 2

Explicație

Pe masă avem un baton de 2 și unul de 3.
A rupe batonul de 3 și mănâncă 1.
B rupe unul dintre batoanele de 2 rămase și mănâncă 2.
A rupe batonul de 2 rămas, mănâncă 2 și jocul se termină.

O altă variantă ar fi fost:
A rupe batonul de 2 și mănâncă 2.
B rupe batonul de 3 ramas și mănâncă 1
A rupe batonul de 2 rămas, mănâncă 2 și jocul se termină.
Această variantă este incorectă pentru că A nu a jucat optim.