율 래즈

아이슬란드 아이들은 운이 좋다. 산타가 한 명이 아니라 $N$명이나 있기 때문이다. 이들은 율 래즈라고 불리며, 크리스마스 이전 $N$일 동안 매일 밤 한 명씩 마을에 내려와 착한 아이에게는 작은 선물을 주고, 말썽꾸러기에게는 감자를 준다.

아이슬란드의 작은 마을에 있는 한 거리에는 $1$번부터 $N$번까지 번호가 매겨진 $N$채의 집이 있다. 각 집은 크리스마스 전구로 아름답게 장식되어 있으며, 처음에는 모든 전구가 켜져 있다.

크리스마스 이전의 $N일$ 동안 매일 밤, 율 래즈 한 명이 이 거리를 방문한다. 크리스마스 $K$일 전에 방문하는 율 래즈는 숫자 $K$를 매우 좋아해서, 집 번호가 $K$의 배수인 집만 방문한다. 또한 율 래즈들은 장난꾸러기라서 방문한 모든 집의 전구 상태를 뒤집는다(켜져 있으면 끄고, 꺼져 있으면 켠다).

그런데 일부 율 래즈는 몸이 아파서 마을에 오지 못했다. 크리스마스 당일에는 $1$번 집을 제외한 모든 집의 전구가 켜져 있었다. 마을에 온 율 래즈는 몇 명인가?

정수 $p$를 정수 $q$로 나눈 나머지가 $0$일 때, $p$는 $q$로 나누어떨어진다고 한다.

첫째 줄에 율 래즈의 수이자 거리의 집 수인 양의 정수 $N$이 주어진다 ($1 \le N \le 10^{13}$).

마을에 온 율 래즈의 수를 나타내는 정수 하나를 출력한다. $1$번 집을 제외한 모든 집의 전구가 켜지는 경우는 정확히 하나만 존재한다고 가정해도 된다.

$N = 6$인 경우를 생각해 보자. 거리에는 집이 여섯 채 있고, 크리스마스 이전의 여섯 밤 동안 일어나는 일은 다음과 같다(율 래즈가 한 명도 아프지 않다고 가정한다).

• 크리스마스 $6$일 전: 율 래즈가 $6$번 집의 전구를 끈다.
• 크리스마스 $5$일 전: 율 래즈가 $5$번 집의 전구를 끈다.
• 크리스마스 $4$일 전: 율 래즈가 $4$번 집의 전구를 끈다.
• 크리스마스 $3$일 전: 율 래즈가 $3$번 집의 전구를 끄고, $6$번 집의 전구를 켠다.
• 크리스마스 $2$일 전: 율 래즈가 $2$번과 $6$번 집의 전구를 끄고, $4$번 집의 전구를 켠다.
• 크리스마스 $1$일 전: 율 래즈가 $1$번과 $4$번 집의 전구를 끄고, $2$, $3$, $5$, $6$번 집의 전구를 켠다.

그러나 실제로는 $4$번 집의 전구가 크리스마스 당일에 꺼져 있었으므로, 위 가정은 실제 상황과 맞지 않는다.

반면 크리스마스 $4$일 전에 왔어야 할 율 래즈만 아팠다면, $1$번 집을 제외한 모든 집의 전구가 크리스마스 당일에 켜져 있게 된다. 따라서 정답은 $5$이다. 크리스마스 $6$, $5$, $3$, $2$, $1$일 전에 온 율 래즈들이 마을에 온 것이다.