Masala #IGLUROK6PL

Xotira 32 MB Vaqt 1000 ms
14
Muallif: Hasan Saleh

Hasan va Ikkilik Funksiya

Quyidagi ikkilik satri ss berilgan bo'lib, u 0 yoki 1 dan iborat; ikkilik satrda ba'zi bir butun son nn ning ikkilik ko'rsatilishi ifodalangan. Sizdan quyidagi ifodani hisoblash so'raladi:

f(n)=log2(n)f(n) = ⌊\log₂(n)⌋

x\lfloor x \rfloor : xx dan kichik yoki teng maksimal butun sonni bildiradi, masalan 3.6 \lfloor 3.6 \rfloor =33 , 1.9999=1 \lfloor 1.9999 \rfloor=1 .

Misol uchun, s=1011s=1011 bo'lsa, u n=11n=11 ni ifodalaydi va f(11)=3f(11)=3 bo'ladi.
 

NOTE : f(0)=0f(0)=0


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son berilgan:  tt  (1t104)(1 \le t \le 10^4) – test holatlarining soni.  

Har bir test holatining birinchi qatori bitta butun sondan iborat:   nn   (1n2105)(1 \le n \le 2 \cdot 10^5) –  ss  satrining uzunligi.  

Har bir test holatining ikkinchi qatori nn uzunlikdagi ikkilik satr ss ni o‘z ichiga oladi.  

Shuningdek, testlarning umumiy  nn  yig‘indisi  21052 \cdot 10^5 dan oshmasligi kafolatlangan.
 


Chiquvchi ma'lumotlar:

Har bir test holati uchun bitta butun son:  f(n)f(n).
 


Misollar
# input.txt output.txt
1
5
2
10
3
111
5
10011
6
111110
6
011010
1
2
4
5
4
Izoh:

Birinchi test holatida  n=2n=2  shunday qilib,  f(2)=1f(2)=1.  

Ikkinchi test holatida  n=7n=7  shunday qilib,  f(7)=2f(7)=2.  

To'rtinchi test holatida  n=62n=62  shunday qilib,  f(32)=5f(32)=5.