Hay piedras sobre la mesa. Por moneda puedes realizar una de las siguientes operaciones:
Quitar una piedra de la mesa. No puedes realizar esta operación si no hay piedras sobre la mesa.
Poner una piedra más sobre la mesa.
¿Cuál es la cantidad mínima de monedas que necesitas gastar para que el número de piedras sobre la mesa sea divisible entre ?
Ten en cuenta que es divisible entre cualquier número, así que si quedan piedras sobre la mesa, la condición del problema se cumple.
La única línea contiene un entero (0 \le n \le 10^9) — la cantidad inicial de piedras sobre la mesa.
Imprime un entero — la cantidad mínima de monedas que necesitas gastar para que el número de piedras sobre la mesa sea divisible entre .
Ejemplo 1
Ejemplo 2
Ejemplo 3
Ejemplo 4
Ejemplo 5
Ejemplo 6
En el primer ejemplo, inicialmente hay piedras sobre la mesa. es divisible entre , así que no necesitas gastar ninguna moneda.
En el segundo ejemplo, puedes pagar una moneda y quitar una piedra de la mesa. Entonces quedarán piedras sobre la mesa, y es divisible entre .
En el tercer ejemplo, puedes pagar una moneda y poner una piedra más sobre la mesa (de modo que haya piedras), y luego pagar otra moneda y poner otra piedra sobre la mesa, obteniendo piedras, que es divisible entre .