Descripción

¡Ya llegó, ya está aquí! Es la gran Posada Sonidera del club de programación y el legendario "LA CHACHACHANGAAAAA" está en las tornamesas controlando el ambiente.

El DJ tiene una pista de cumbia muy especial llamada "El Baile del Entero", que empieza con una velocidad (BPM) de \(N\).

Para que la fiesta explote y la gente saque "los pasos prohibidos", el Sonidero quiere transformar la canción hasta llegar al Ritmo Legendario, que tiene una velocidad de exactamente 1.

Para lograrlo, el DJ solo tiene dos botones en su consola de mezclas:

1. "¡Échale Loop!" (\(\times 2\)): Puede duplicar la velocidad de la pista (multiplicar \(N\) por 2).

2. "¡La Rebajada!" (\(/ 6\)): Puede aplicar un efecto de Cumbia Rebajada que divide la velocidad entre 6. (Ojo: Este botón solo funciona si la velocidad actual es divisible exactamente entre 6; si no, la consola se quema).

Tu misión, como chalán del Sonidero, es decirle cuál es el número mínimo de movimientos (botones que debe apretar) para llevar la canción desde la velocidad \(N\) hasta el Ritmo Legendario 1.

Si la canción está "salada" y es imposible llegar al 1 con esos efectos, tendrás que decirle al DJ que cambie de rola (imprimiendo -1).

Entrada

La primera línea contiene un entero \(T\) (\(1 \le T \le 2 \cdot 10^4\)) — el número de canciones que intentará mezclar el Sonidero.

Cada caso contiene un entero \(N\) (\(1 \le N \le 10^9\)) — la velocidad inicial de la cumbia.

Salida

Para cada canción, imprime el número mínimo de movimientos para llegar a 1. Si no se puede, imprime -1.

Ejemplos

Entrada

7
1
2
3
12
12345
15116544
387420489

Salida

0
-1
2
-1
-1
12
36

Notas del Sonidero

• Caso \(N=1\): ¡Ya estás en el ritmo, papá! (0 movimientos).

• Caso \(N=2\): Tienes un 2. No puedes dividir entre 6. Si multiplicas (\(2 \times 2 = 4\)), te alejas más. ¡Esa rola no sirve! (-1).

• Caso \(N=3\):

  1. ¡Échale Loop! (\(3 \times 2 = 6\)).

  2. ¡La Rebajada! (\(6 / 6 = 1\)).

  Total: 2 movimientos.