În ultima sa expediție pe Terra, Tassadar, liderul Protoss, s-a îndrăgostit de Miruna. Pentru a-i câștiga inima, Miruna îi cere să rezolve un set de provocări.
Dându-se numerele naturale N, A și B, Tassadar trebuie să găsească înălțimea minimă a unui arbore binar care conține cel puțin N noduri, știind că muchiile către fiii din stânga ai fiecărui nod au lungime A, iar muchiile către fiii din dreapta au lungime B.
Cerinţă
Pentru T astfel de provocări, găsiți înălțimea cerută și ajutați-l pe Tassadar să o cucerească pe Miruna!
Date de intrare
Fişierul de intrare provocare.in conţine pe prima linie un singur număr natural T reprezentând numărul de provocări. Pe următoarele T linii se află câte 3 numere naturale separate prin câte un spaţiu, N, A și B cu semnificația din enunț.
Date de ieşire
În fişierul de ieşire provocare.out se vor afișa T linii. Pe fiecare linie va fi scris câte un singur număr natural, reprezentând răspunsul la câte o provocare, în ordinea dată în fișierul de intrare.
Restricţii si precizări
1 ≤ T ≤ 51 ≤ N, A, B ≤ 1 000 000 000- Pentru
10%din testeN, A, B ≤ 100 - Pentru alte
10%din testeN ≤ 100 000 - Pentru alte
10%din testeN ≤ 1 000 000 - Pentru alte
15%din testeA, B ≤ 10 000 - Este vorba despre aceeași Miruna ”legendară” și binecunoscută la concursurile de informatică
Exemple
provocare.in
4
2 1 2
4 2 1
100 13 17
100000 127 81
provocare.out
1
2
90
1642
Explicaţie
Pentru prima provocare, se construiește un arbore binar care are doar rădăcina cu un fiu stâng. Pentru a doua provocare, se construiește un arbore binar care are rădăcina cu ambii fii, iar fiul drept are, și el, un fiu drept