Los ingenieros electrónicos de IslaGrande construyeron para la enseñanza de la aritmética en las escuelas primarias un extraño equipo de cómputo que solamente tiene al número ~1~ como constante e implementadas las operaciones de sumar y multiplicar. Para eliminar esta limitación el equipo tiene una potente memoria en la cual los resultados previos de las etapas anteriores se guardan y luego pueden ser utilizados como operandos en las etapas posteriores. Todas las operaciones posibles de una etapa se ejecutan de manera simultánea.

Tomemos como ejemplo a ~N = 7~, en qué etapa lo podemos obtener ?. Naturalmente comenzaremos partiendo de la constante ~1~, así en la primera etapa solamente obtenemos el ~2 (= 1 + 1)~, pues multiplicando ~1 * 1~ no se genera un número nuevo. En la segunda etapa para los números previos ~1~ y ~2~ obtendríamos el ~3 (= 2 + 1)~ y el ~4 (=2 + 2 = 2 * 2)~. Entonces en la tercera etapa aparecería el número ~7 (= 4 + 3)~. Para ~N = 11~, este aparece en la cuarta etapa como: ~11 = 7 + 4 = 8 + 3 = 9 + 2~, pero no como ~10 + 1~ ya que el ~10~ aparece también en la cuarta etapa.

Determinar la etapa en la cual aparece un número ~N (1 \leq N \leq 10,000)~ entrado.

Entrada

La entrada contiene en una sola línea a ~N~.

Salida

La salida contiene en una sola línea un entero simple, el cual representa el número de la etapa en la cual aparece el número ~N~.

Ejemplo de Entrada

26

Ejemplo de Salida

5

Explicación

Después del tercer paso tenemos: ~{ 1 2 } { 3 4 } { 5 6 7 8 9 12 16}~. Con ninguna pareja de estos elementos podemos formar el ~26~ en el cuarto paso. Con ellos, no obstante, podemos lograr el ~13 (13 = 7 + 6 = 8 + 5 = 9 + 4 = 12 + 1)~ en el cuarto paso. Entonces el ~26 (= 2 * 13~, por ejemplo) lo obtendríamos en el quinto paso.