Cerință

Se dau trei numere naturale, $a$, $b$ și $k$. George, fiind pasionat de matematică și informatică, a inventat un algoritm, iar acum el vrea să vă testeze cunoștințele de informatică pentru a afla răspunsurile cerute de el.

Algoritmul descris de George funcționează în modul următor:

Cât timp $a$ și $b$ sunt diferite, afișăm pe o linie nouă $a$ și $b$ și vom scădea din numărul mai mare, numărul mai mic.

De exemplu, dacă la început $a = 14$ și $b = 39$, primele $5$ perechi de valori afișate sunt

• $14 \ 39$ (prima pereche)
• $14 \ 25$ (din $b$ s-a scăzut $a$)
• $14 \ 11$ (din $b$ s-a scăzut $a$)
• $3 \ 11$ (din $a$ s-a scăzut $b$)
• $3 \ 8$ (din $b$ s-a scăzut $a$)

Acum, George vrea să știe ce valori vor avea $a$ și $b$ la cel de-al $k$-lea pas.

Practic, dacă $k$ ar fi $3$, trebuie afișat $14 \ 11$.

Deoarece acest lucru este prea ușor, el vă cere să rezolvați problema pentru $t$ astfel de triplete. El vă garantează că algoritmul va afișa cel puțin $k$ linii.

Date de intrare

Pe prima linie a fișierului de intrare operatii.in veți citi $t$, numărul de triplete pentru care trebuie să rezolvați problema.

Pe următoarele $t$ linii, se dau tripletele, conținând $a \ b \ k$, cele trei numere din triplet.

Date de ieșire

Pentru fiecare triplet, afișați pe o linie separată a fișierului operatii.out valoarea lui $a$ și valoarea lui $b$ după $k$ pași.

Restricții și precizări

• $1 \leq t \leq 1 \ 000$;
• $1 \leq a, b, k \leq 10^9$;
• Algoritmul va afișa cel puțin $k$ linii.
• Pentru teste în valoare de $15$ de puncte, $(t = 1)$ și $(1 \leq a, b, k \leq 10^6)$.
• Pentru teste în valoare de $25$ de puncte, $(1 \leq t \leq 5)$ și $(1 \leq a, b, k \leq 10^6)$.

Exemplu

operatii.in

2
14 39 3
167 96 7

operatii.out

14 11
17 4

Explicație

Pentru prima pereche, explicația se găsește în enunț.

Pentru cea de-a doua pereche, valorile lui $a$ și $b$ se schimbă în felul următor:

• $167 \ 96$
• $71 \ 96$
• $71 \ 25$
• $46 \ 25$
• $21 \ 25$
• $21 \ 4$
• $17 \ 4$

Vom afișa $17 \ 4$.