Los marcianos harán todas las cosas posibles para que sus naves espaciales no sean vistas por los terrícolas. Como sus naves han sido inventadas recientemente, una vía espacial ha sido construida para probarlas. Esta vía está representada por un rayo cuyo origen se encuentra en el centro del Sol. La ubicación de algún objeto en el rayo marciano es la distancia desde el objeto hasta el Sol medida en años luz.

Las pruebas a las naves espaciales se realizarán de la siguiente manera: el primer día incluye la instalación de la nave en la vía a una distancia de un año luz del Sol, durante cada uno de los próximos días la nave debe recorrer una distancia igual al número máximo en notación decimal a la distancia del Sol a la nave temprano en la tarde en la tarde. Por ejemplo, si temprano en el día la nave estaba a una distancia de 132 años luz del Sol, ese día la nave tiene que recorrer una distancia de 3 años luz, si por el contrario estuviera a una distancia de 932 años luz del Sol entonces recorría 9 años luz. Las naves vencen la distancia programada muy rápidamente, así que es posible verlas a ellas solamente al comienzo de un día.

Los terrícolas instalaron un equipo rastreador en la vía a una distancia de ~N~ años luz del Sol. Ayude a determinar si la nave marciana no será vista, y si es así, calcule el número de días necesarios que deben pasar para poder ver la nave.

Entrada

La única línea de la entrada contiene un entero simple ~N (1 \le N \le 10^{18}~ ) — la distancia desde el Sol al equipo rastreador.

Salida

La única línea de la salida contiene un entero positivo – el número de días que son necesarios para poder ver la nave, y ~-1~, si la nave no será vista.

Ejemplo 1 de Entrada

22

Ejemplo 1 de Salida

6

Ejemplo 2 de Entrada

3

Ejemplo 2 de Salida

-1

Explicación del primer ejemplo:

En cada uno de los seis días respectivamente la nave arribó a las distancias: ~1, 2, 4, 8, 16~ y ~22~, esta última donde estaba ubicado el equipo rastreador.

Evaluación

• Subtarea 1 (20 puntos) ~N \le 100~.

• Subtarea 2 (20 puntos) ~N \le 10^5~.

• Subtarea 3 (20 puntos) ~N \le 10^9~.

• Subtarea 4 (20 puntos) ~N \le 10^{12}~.

• Subtarea 5 (20 puntos) sin restricciones adicionales.