410169: GYM103967 E Эффективный двигатель

Как известно, тарелка Рика летает, используя энергию, вырабатываемую обитателями карманной вселенной, созданной самим Риком. После прошлого инцидента Рик долго размышлял, какие меры предосторожности принять, чтобы снова не оказаться без возможности завести летающую тарелку в самый неподходящий момент, и наконец придумал следующее решение.

Рик решил, что теперь под капотом тарелки будет находиться не одна карманная вселенная, а целых $$$n$$$. При чем, чтобы жители этих карманных вселенных не успевали развивать свои цивилизации до такого уровня, на котором они смогут сами изобрести свои карманные вселенные, некоторые из них Рик периодически будет перезапускать.

Изначально все $$$n$$$ карманных вселенных находятся в замороженном состоянии и не функционируют. Механизм перезапуска устроен следующим образом: перед $$$i$$$-м полетом летающей тарелки Рик по очереди пройдется по всем вселенным, номера которых делятся на $$$i$$$ (включая саму $$$i$$$-ю), и поменяет их состояние:

• если соответствующая вселенная была заморожена или была раньше перезапущена, Рик спустится в нее и представит ее обитателям технологию, которая позволит им вырабатывать для него энергию;
• если же вселенная уже функционировала, Рик отправляет ее на перезапуск, откатывая развитие цивилизации в ней на стартовую ступень.

Если в какой-то момент перед полетом оказывается, что ни одна вселенная не готова к вырабатыванию энергии, на этот случай у Рика есть одна запасная, так что беспокоиться не о чем.

Теперь Рика интересует, сколько вселенных будут функционировать после первых $$$n$$$ полетов летающей тарелки. Помогите ему посчитать это количество. Полеты нумеруются от $$$1$$$ до $$$n$$$, как и карманные вселенные.

В единственной строке дано число $$$n$$$ — количество карманных вселенных, установленных в летающую тарелку $$$(1 \leqslant n \leqslant 10^{18})$$$.

В единственной строке выведите ответ на задачу.

2

1