Vale se está preguntando de cuantas formas se puede generar una lista de números aleatorios que inicia en N, como Vale tiene un poco de flojera escribir cada uno de los números de esta lista que puede ser demasiado grande, ella quiere crear un algoritmo que haga ese trabajo, y le permita ahorrar sus energías.

Vale piensa en el siguiente método:
- Inicia con un número entero positvo cualquiera.
- Si el número es par, entonces lo divide entre dos.
- Si el número es impar, entonces lo multiplica por tres y le suma una unidad.

Ella va realizando estas operaciones y obteniendo números diferentes hasta llegar a 1, cuando el último número generado es 1, ella detiene el proceso. veamos el siguiente ejemplo:

Tu tarea es imprimir un solo número, que será la cantidad de elementos en la lista generada por el algoritmo de Vale que inicia en N. Teniendo en cuenta el ejemplo anterior, tu respuesta sería 7.

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 contiene el entero N ( 1 ≤  N  ≤ 100000000 ) Que será el número con el que Vale iniciará la lista.

Output

Imprimir un número, que será la cantidad de elementos que contiene la lista generada.

Entrada de ejemplo