Description

Una secuencia que consiste en un dígito, el número 1 es escrito inicialmente en un computador. En cada paso sucesivo de tiempo, el computador transforma simultáneamente cada dígito 0 en la secuencia 1 0 y cada dígito 1 en la secuencia 0 1. Así, después del primer paso de tiempo, se obtiene la secuencia 0 1; después del segundo paso, la secuencia 1 0 0 1, después del tercer paso, la secuencia 0 1 1 0 1 0 0 1 y así sucesivamente.

¿Cuántos pares de ceros consecutivos aparecerán en la secuencia después de n pasos?

Input

Toda línea de entrada contiene un número natural n (0 < n <= 1000).

Output

Para cada n de la entrada imprima el número de ceros consecutivos que aparecerán después de n pasos.

2
3

1
1

Source

Southeastern Europe 2005

Translator

Steinersp