Юбилей
В 2134 году, когда население Земли достигло 10^18 человек, было решено отметить это событие следующим образом. На огромной территории, специально отведенной под празднование, было размещено N миниатюрных лампочек (линейные размеры одной лампочки составляли менее 0.1 миллиметра), некоторым образом пронумерованных последовательными числами от 1 до N.
Изначально все лампочки были выключены. Далее было произведено ровно 10^18 шагов — по одному в честь каждого жителя Земли. На i-ом шаге одновременно изменялось состояние всех лампочек, номера которых делятся нацело на i. Изменение состояния означает, что если лампочка была выключена, то она становится включенной, и наоборот, если лампочка была включена, то она становится выключенной. Промежуток времени между последовательными шагами составил 1 пикосекунду, таким образом, все празднование заняло порядка полутора недель.
Вообще, для сторонних наблюдателей все это выглядело как беспорядочное бессмысленное мерцание, тем не менее, все были в восторге — настолько очевиден был грандиозный масштаб этого замечательного мероприятия!
Но вот все закончилось. Смотреть стало не на что и, как показал более трезвый анализ, смотреть, собственно, и было не на что.
Тем временем, после выполнения шага 10^18, некоторые лампочки остались во включенном состоянии. Пока жители Земли отходят от шока, размышляя о том, зачем им понадобилось подобное празднование и как теперь покрыть баснословные затраты на всю эту впечатляющую ерунду, вам предлагается посчитать количество лампочек, которые все еще горят и расходуют драгоценную электроэнергию.
Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 2^63 - 1).
Выходные данные
Выведите единственное целое число — количество лампочек, которые остались во включенном состоянии по завершении шага с номером 10^18.