La un concurs de maraton participă N broscuţe. Fiind un concurs mai special, fiecare broscuţă are de parcurs propriul traseu, a cărui lungime se cunoaşte şi pe care trebuie să îl parcurgă efectuând cât mai puţine salturi. Pentru a nu fi descalificată, în urma ultimului salt efectuat trebuie să ajungă exact în punctul de finish. Înainte de start fiecărei broscuţe i se comunică două numere naturale distincte reprezentând lungimile salturilor pe care are voie să le execute în timpul maratonului. Cu alte cuvinte, o broscuţă aflată în concurs trebuie să ajungă în punctul de finish al traseului ei, efectuând doar două tipuri de salturi, lungimile acestora fiind impuse de organizator.
Cerinţă
Scrieţi un program care determină pentru fiecare din cele N broscuţe, numărul minim de salturi necesar fiecăreia pentru a atinge punctul de final al traseului repartizat, cunoscând lungimile salturilor pe care le poate efectua.
Date de intrare
Fişierul de intrare oak.in conţine pe prima linie numărul natural N. Următoarele N linii conţin triplete de numere naturale Ai Bi Ti cu semnificaţia broscuţa cu tricoul numărul i va efectua doar salturi de lungimi Ai sau Bi, iar traseul repartizat ei are lungimea Ti. Broscuţele sunt numerotate de la 1 la N, în ordinea din fişierul de intrare.
Date de ieşire
Fişierul de ieşire oak.out va conţine N linii. Pe linia i a fişierului se va scrie numărul minim de salturi necesar broscuţei i pentru a atinge punctul de final al traseului repartizat, sau –1 dacă broscuţa nu va reuşi să-l atingă.