감옥이 n개가 있었습니다. 감옥 하나에 1명의 죄수가 들어있습니다.

그런데, 어느날 간수랑 로비라도 했는지, 간수가 1번 방의 죄수에게 열쇠를 줘버립니다.

그래서 죄수는 나오기로 결심을 했지요.

그런데, 감옥 하나에 일일이 다른 열쇠 만들기도 귀찮았는지, 그 열쇠가 모든 감옥을 열 수 있게 되어있었던것이지요.

그래서, 이 멋진놈은 나오면서 99개의 감옥을 다 풀어버렸습니다!

근데 문제는 여기서 발생합니다.

속좁은 죄수놈들이 중범죄를 가진게 아닌지라 나갈까 말까 고민을 합니다.

그사이에, 2번째 죄수가 감옥에서 나오면서, 갑자기 짝수번 감옥을 다 닫아버립니다.

그러자, 3번 죄수는 그게 재밌어 보였는지, 나오면서 3의 배수에 해당하는 감옥을 닫힌건 열고 열린건 닫습니다.

그런식으로 더이상 나올 수 있는 죄수가 없을때까지 번호 순서대로 나와서 같은 행위를 계속 합니다.

예를 들어

n=10이면

1 2 3 4 5 6 7 8 9 10

첫번째 죄수는 나가면서 다엽니다. 나간걸 f, 닫힌건 c,  열린건 o라 합시다.

f o o o o o o o o o

그리고 두번째 죄수는, 짝수번을 닫습니다.

f f o c o c o c o c

세번째 죄수는, 3의 배수를 닫힌건 열고 열린건 닫습니다.

f f f c o o o c c c

네번째 죄수는, c라서 못나갑니다.

f f f c o o o c c c

다섯번째 죄수는, 5의 배수를 닫힌건 열고, 열린건 닫습니다.

f f f c f o o c c o

여섯번째 죄수도 마찬가지

f f f c f f o c c o

일곱번째는

f f f c f f f c c o

여덟번째는 못나가죠.

f f f c f f f c c o

아홉번째도 못나갑니다.

f f f c f f f c c o

열번째가 나가면!

f f f c f f f c c f

따라서, 나간사람이 일곱, 못나간사람이 셋이죠. 이게 10개일때입니다.

문제는 주어진 n에 대하여 나간 사람의 수를 출력하는겁니다.

입력

출력

입출력 예

입력

10

출력

7

출처:cryptographer