Древние греки и римляне считали, что боги подземного мира любят чётные числа, а боги, охраняющие живых, — нечётные. В 123 году нашей эры Риму грозила война с Парфянским царством. Император Адриан хотел избежать кровопролития и отправился на переговоры с парфянами. Чтобы боги даровали Адриану великое красноречие, он решил принести им в жертву стадо из n баранов. Разумеется, число n было нечётным. Поразмыслив, Адриан понял, что каждому богу нужно принести в жертву одинаковое число баранов, иначе бог, получивший меньше баранов, разгневается на Адриана и помешает ему решить вопрос мирным путём.

Император позвал к себе математика Теона Смирнского и приказал ему поделить стадо баранов на равные части. Теон Смирнский также был суеверен, поэтому подумал, что количество богов, которым нужно принести жертвы, должно не только быть нечётным, но и иметь нечётное число положительных делителей. По-видимому, он смог решить эту задачу — переговоры с Парфией прошли успешно. А можете ли решить её вы?

В единственной строке записано целое нечётное число n (1 ≤ n ≤ 10¹⁸ − 1).

Выведите, какому количеству богов нужно было принести жертвы. Если задача имеет несколько решений, выведите максимальное из них.