[579A] Criando bacterias

Enlace a Codeforces

Eres un amante de las bacterias, y quieres reunir cierto número de bacterias en una caja.

Inicialmente, la caja está vacía. Cada mañana, colocas cierta cantidad de bacterias en la caja. Y cada noche, cada bacteria dentro de la caja se divide en dos bacterias. Tras cierto tiempo, esperas ver exactamente $x$ bacterias dentro de la caja.

¿Cuál es el mínimo de bacterias que debes colocar dentro de la caja para tener en algún momento cierta cantidad exacta de bacterias?

Entrada

Un entero $x$ ($1 \leq x \leq 10^9$)

Salida

Un entero: la respuesta

Ejemplos

input:
5

output:
2

input:
8

output:
1

Nota

En el primer ejemplo, podemos añadir una bacteria en la mañana del primer día, y en la mañana del tercer día tendremos 4 bacterías en la caja. Colocando una más esta misma mañana, entonces obtenemos las 5 que queremos. En total, añadimos 2 bacterias en el proceso, y por lo tanto, la respuesta es 2.

En el segundo ejemplo, colocamos una durante la primera mañana y en la mañana del cuarto día tendremos 8 bacterias en la caja. Por lo tanto, la respuesta es 1.