Î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 ≤ 5
• 1 ≤ N, A, B ≤ 1 000 000 000
• Pentru 10% din teste N, A, B ≤ 100
• Pentru alte 10% din teste N ≤ 100 000
• Pentru alte 10% din teste N ≤ 1 000 000
• Pentru alte 15% din teste A, 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