Zadanie

Je to dôležitá veda

Počet bodov: 60

Koľko batoliat je potrebných na výmenu žiarovky? Kolko dážďoviek napíše náhodným pohybom po písacích strojoch Hamleta za rok? Koľko dní je potrebných na odoslanie gumenných koní? Dôležité otázky. Je možné robiť experimenty, pri ktorých pre konkrétne číslo zistíte, či je postačujúce alebo nie. Odpoveď však treba zistiť rýchlo. Našťastie ste po rokoch analýzy výpočtovej a pamäťovej zložitosti už dostatočne otupení na to, aby vás nezaujímalo presné číslo, ale iba dolný a horný odhad.

Úloha

Zaujíma vás približný dolný a horný odhad. Pre jednoduchosť vám už nejaké počiatočné odhady poskytneme - \(d\) je ešte príliš málo, ale \(h\) už je dosť. Dostanete zadanú požadovanú presnosť a vašou úlohou je zistiť, koľko najmenej meraní je ešte nutné vykonať, aby bol pomer horného a dolného odhadu nanajvýš daná presnosť.

Vstup a Výstup

V prvom riadku vstupu je číslo \(1 \leq O \leq 10^4\) - počet otázok na vstupe. Nasleduje \(O\) riadkov, na každom tri celé čísla \(d_i\), \(h_i\), \(p_i\) - dolný odhad, horný odhad a požadovaná presnosť, pricom \(1 \leq d_i \leq h_i \leq 10^9\) a \(2 \leq p_i \leq 10\).

Na výstup vypíšte \(O\) riadkov, na každom z nich odpoveď na príslušnú otázku - koľko najmenej meraní je potrebných spraviť aby bol pomer horného a dolného odhadu nanajvýš požadovaná presnosť.

Vstup bude obsahovať viacero obtiažností sád. Bude \(8\) sád, v \(s\)-tej bude \(h_i \leq 10^{1+s}\). Navyše v prvých dvoch bude \(p_i = 2\).

Príklady

Input:

4
7 15 2
7 15 3
5 46 3
9 150 2

Output:

1
0
2
3

Pre prvú otázku môžeme otestovať napríklad 10. Ak experiment vyjde, naše odhady budú 7,10 a ak nevyjde, tak 10,15. Bezohľadu na výsledok tak na jedno meranie dosiahneme dostatočnú presnosť.

Pre tretiu otázku môžeme otestovať napríklad 16. Ak experiment vyjde, náš horný odhad bude 16, čo nie je dosť presné s dolným odhadom 5, a budeme musieť experimentovať znovu. Ak by sme však otestovali 15, a experiment nevyjde, náš dolný odhad bude 15, čo zas nie je dosť presné s horným odhadom 46. Tým pádom potrebujeme bezohľadu na našu stratégiu v najhoršiom prípade aspoň dva experimenty (a s nimi to už zvládneme).