PascalN девченок стоят в круге и кидают мяч друг другу. Девочка,

Pascal

N девченок стоят в круге и кидают мяч друг другу. Девченка, у которой мяч был в начале забавы, кидает мяч K-й после нее девченке, считая по часовой стрелке (1KN/2). Эта девочка ловит мяч и в свою очередь кидает мяч K-й после нее девченке, считая по часовой стрелке, и так далее. Так мяч перебегает от девочки к девченке до тех пор, пока он снова не попадет к девочке, у которой мяч был в самом начале игры. К примеру, если N = 7 и K = 3, то девочки получают мяч в последующем порядке: 1, 4, 7, 3, 6, 2, 5, 1.

Чтобы сделать забаву еще более интересной, девочки желают избрать K как можно более великим, но с тем, чтоб выполнялось одно условие: во время игры мяч должен побывать у каждой девочки хотя бы один раз.

Входные данные

Ваша программка должна вводить с клавиатуры одно число N (3N2000000000) количество девченок, принимающих роль в забаве.

Выходные данные

Выведите на экран число K, которое необходимо избрать девочкам.

Образцы.

Ввод
Вывод