A robin le encantan las matemáticas. Es por eso que cuando se aburre, juega con un número realizando algunas operaciones. Hoy Robin tiene un nuevo juego.

Robin tiene un número entero positivo X, y quiere realizar operaciones sobre este hasta conseguir el número "1" de la misma. Mientras que X no sea igual a "1", Robin repite la siguiente operación:

Si X es impar, entonces suma 1 al mismo, de lo contrario si X es par, divide entre 2. Robin sabe que para cualquier número entero positivo el proceso termina en un tiempo finito. ¿Cuántas acciones debería realizar Robin para conseguir un número "1" del número X?.

Tenga en cuenta que el número X viene representado en su notación binaria. Se garantiza que el primer dígito de X es diferente de cero y el número de sus dígitos no excede de 10 ^ 6.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La única línea de cada caso contiene un número entero positivo X representado en un sistema binario.

Output

Salida. Imprimir el número necesario de operaciones para convertir el número X en 1.

Entrada de ejemplo

Explicación

Vamos a considerar el tercer caso de ejemplo. El número 101110 es par, lo que significa que debemos dividir entre 2. Después de de esta operación se obtiene un número impar 10111 entonces se suma uno. Ahora tenemos el número 11000, este se puede dividir entre 2, tres veces y se obtiene el número de 11. Como este es impar aumentamos el número en uno y obtenemos 100, por último dividimos el número entre 2, dos veces seguidas. Como resultado final se obtiene 1, y el número de operaciones, 8.