D. Enzo, o Mágico
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

O Mágico Enzo fará uma apresentação na UnB (Universidade de Baralhos), e para isso está treinando uma forma de embaralhar cartas chamado Embaralhamento Mágico.

Vamor denotar um baralho de $$$n$$$ cartas como um vetor $$$a$$$ de tamanho $$$n$$$. O embaralhamento funciona da seguinte forma: separamos os elementos de posições ímpares (indexado em $$$1$$$) no vetor $$$l$$$ e os elementos de posições pares no vetor $$$r$$$. Depois concatenamos $$$r$$$ em $$$l$$$ ($$$a = l + r$$$).

Um truque conhecido é embaralhar o baralho vezes o suficiente para que ele volte ao estado inicial. Ajude Enzo e calcule quantos Embaralhamentos Mágicos é necessário para que um baralho de $$$n$$$ cartas distintas volte ao seu estado inicial.

Input

A única linha de entrada contém um inteiro par $$$n$$$ $$$(1 \leq n \leq 10^6)$$$, o tamanho do baralho.

Output

Imprima um único inteiro positivo: a menor quantidade de Embaralhamentos Mágicos para que o baralho volte a seu estado inicial.

Examples
Input
8
Output
3
Input
6
Output
4
Input
1000000
Output
180
Note

Vamos denotar as 8 cartas do baralho por $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$. O embaralhamento leva este baralho ao vetor $$$[1, 3, 5, 7, 2, 4, 6, 8]$$$. A sequência inteira fica:

$$$[1, 2, 3, 4, 5, 6, 7, 8]$$$ ->

$$$[1, 3, 5, 7, 2, 4, 6, 8]$$$ ->

$$$[1, 5, 2, 6, 3, 7, 4, 8]$$$ ->

$$$[1, 2, 3, 4, 5, 6, 7, 8]$$$,

dando a resposta $$$3$$$.