Počet bodov:
Popis:  12b
Program:  8b

Prichádza zima a každý chce byť pekne v teplúčku. Lomižaba sa pripravil: dal si na intráku namontovať zbrusu nové kachle. Teraz, spokojný sám so sebou, aké dobré kachle kúpil, si hovie v postielke, no nejako mu je stále bez periny zima.

“Ja ťuťmák!”, vyskočil Lomižaba z postele, “Zabudol som dreva nakúpiť!” Rýchlo schytil nejakého FKS-áka a dal mu vyrátať, koľko dreva potrebuje na vykúrenie svojej útulnej izbietky. “Potrebuješ \(k\) metrov.” oznámil FKS-ák po vypísaní troch traktorákov.

Kde ale teraz zoženie drevo? Lomižaba prebehol všetky obchody, no dobré drevo už bolo vykúpené! Posledný predajca si ale všimol, že Lomižaba je zo svojej situácie veľmi smutný. “Počkaj chlapče! Vidím, že junák si mi statný. Mal by som pre teba sáhovicu, no nemám žiadnu pílu.” ponúkol mu predajca. “Jasné, pílu nepotrebujem ujo, nevolám sa predsa Lomižaba len tak pre nič za nič. Mojim učiteľom Kálania Smrekových Pňov bol sám slávny Lomidrevo.” Pomôžte Lomižabovi nalámať sáhovicu.

Úloha

Dĺžka sáhovice v metroch je mocnina dvojky. Lomižaba vie ľubovoľný kus dreva zlomiť na polovicu. Lomižaba potrebuje nalámať sáhovicu na niekoľko kusov tak, aby sa spomedzi nich dali vybrať nejaké s celkovou dĺžkou presne \(k\).

Vašou úlohou je zistiť najmenší možný počet lámaní, ktoré na to potrebuje.

Formát vstupu

Na prvom riadku vstupu bude číslo \(t ~ (1 \leq t \leq 3000)\), ktoré označuje počet otázok, na ktoré máte odpovedať.

Každá otázka je zadaná na jednom riadku vstupu. Tento riadok obsahuje dve celé čísla \(n, k ~ (0 \leq n \leq 10^{18}\) a \(1 \leq k \leq 10^{18})\) oddelené medzerou. Sáhovica má \(2^n\) metrov a Lomižaba ju chce nalámať na kusy, z ktorých sa dá vyskladať sáhovica dĺžky \(k\) metrov. Vždy bude platiť \(2^n \geq k\) (sáhovica je teda dostatočne dlhá).

Formát výstupu

Pre každú otázku vypíšte na samostatný riadok jedno číslo, a to najmenší možný počet lámaní, ktorým vieme z našej sáhovice spraviť kusy také, že sa z nich dá poskladať sáhovica dĺžky \(k\).

Môžete predpokladať, že sa to vždy bude dať.

Hodnotenie

Vaše riešenia budú testované na štyroch sadách testovacích vstupov, pre ktoré platí:

Sada 1 2 3 4
Maximálne \(n\) \(3\) \(6\) \(1000\) \(10^{18}\)
Maximálne \(k\) \(8\) \(16\) \(10^6\) \(10^{18}\)

Všimnite si, že čísla \(n\) a \(k\) v \(4.\) sade presiahnu \(2^{31} - 1\), čo je najväčšie číslo, ktoré sa dá uložiť v \(32\)-bitovej premennej so znamienkom. Použite preto \(64\)-bitové premenné typu long long v C++ a Int64 v Pascale.

Príklad

Input:

3
3 8
2 3
123456789 109051904

Output:

0
2
123456766

V prvej otázke dostaneme sáhovicu rovno s dĺžkou \(8\), preto ju lámať nemusíme.

V druhej otázke už musíme lámať aspoň \(2\)-krát. Po prvom rozlomení máme \(2\) kusy po \(2 \textrm{m}\). Teraz stačí rozlomiť ešte jeden \(2\)-metrový kus. Z kusov s veľkosťami \(2, 1, 1\) môžeme vybrať \(2\)-metrový a jeden \(1\)-metrový, s celkovou dĺžkou \(3\) metre.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.