시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB44302369.697%

문제

The kids in Iceland are pretty lucky. Not only do they have one Santa Claus, but N of them! They’re called the Yule Lads, and on each of the N nights before Christmas, one of them comes to town, giving those that have been nice a small present, and those that have been naughty a potato.

On a street in a small town in Iceland, there are N houses, numbered in turn from 1 to N. Each house is beautifully decorated with Christmas lights, and initially they are all turned on.

On each of the N nights before Christmas, one of the Yule Lads visits this street. The Yule Lad visiting K nights before Christmas is very fond of the number K, and will only visit the houses whose house number is divisible1 by K. Furthermore, the Yule Lads are troublemakers, and will toggle the state of the Christmas lights on every house that they visit (i.e. turning the lights off if they are on, or turning them on if they are off).

However, some of the Yule Lads have been feeling sick, and did not come to town. On Christmas day all but the first house had their lights turned on. How many Yule Lads came to town?

1An integer p is divisible by the integer q if the division p/q leaves no remainder.

입력

The first line of input contains a positive integer N, the number of Yule Lads and the number of houses in the street.

출력

Output a single integer, the number of Yule Lads that came to town. You can assume that there is only one scenario that leads to all houses having their lights on except for house number 1.

서브태스크 1 (15점)

  • N ≤ 13

서브태스크 2 (10점)

  • N ≤ 1000

서브태스크 3 (12점)

  • N ≤ 105

서브태스크 4 (13점)

  • N ≤ 5 · 106

서브태스크 5 (15점)

  • N ≤ 108

서브태스크 6 (14점)

  • N ≤ 1010

서브태스크 7 (21점)

  • N ≤ 1013

예제 입력 1

6

예제 출력 1

5

예제 입력 2

13

예제 출력 2

9

예제 입력 3

68

예제 출력 3

42

힌트

Consider the case N = 6. Then there are six Yule Lads, and six houses in the street. Here is what happens on each of the six nights before Christmas, assuming that no Yule Lad is sick.

  • Six nights before Christmas, the Yule Lad will turn the lights at house 6 off.
  • Five nights before Christmas, the Yule Lad will turn the lights at house 5 off.
  • Four nights before Christmas, the Yule Lad will turn the lights at house 4 off.
  • Three nights before Christmas, the Yule Lad will turn the lights at house 3 off, and the lights at house 6 on.
  • Two nights before Christmas, the Yule Lad will turn the lights at houses 2 and 6 off, and the lights at house 4 on.
  • The night before Christmas, the Yule Lad will turn the lights at houses 1 and 4 off, and the lights at houses 2, 3, 5 and 6 on.

However, house number 4 has its lights off on Christmas day, contrary to what actually happened.

On the other hand, if only the Yule Lad that was supposed to come into town four days before Christmas is sick, then all lights, except for at house number 1, will be lit on Christmas day. The correct answer is thus 5: Yule Lads came to town 6, 5, 3, 2 and 1 days before Christmas.