율 라드

아이슬란드의 아이들은 꽤 운이 좋다. Santa Claus가 하나뿐만 아니라, 무려 $N$이나 있기 때문이다! 이들은 Yule Lads(이)라고 불리며, 크리스마스 전 $N$일 동안 매일 밤 한 명씩 마을에 와서 착하게 지낸 아이에게는 작은 선물을, 말썽을 부린 아이에게는 감자를 준다.

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

크리스마스 전 $N$일 동안 매일 밤 Yule Lads 중 한 명이 이 거리를 방문한다. 크리스마스 $K$일 전에 방문하는 율 라드는 수 $K$(을)를 매우 좋아하므로, 집 번호가 $K$(으)로 나누어떨어지는 집만 방문한다(정수 $p$(이)가 정수 $q$(으)로 나누어떨어진다는 것은 나눗셈 $p/q$(이)가 나머지를 남기지 않는다는 뜻이다). 또한 Yule Lads(은)는 말썽꾸러기이므로 방문하는 모든 집의 크리스마스 전구 상태를 반대로 바꾼다(즉, 전구가 켜져 있으면 끄고 꺼져 있으면 켠다).

하지만 Yule Lads 중 일부는 몸이 아파서 마을에 오지 못했다. 크리스마스 당일에는 첫 번째 집을 제외한 모든 집의 전구가 켜져 있었다. 마을에 온 Yule Lads(은)는 몇 명인가?

예제

$N = 6$인 경우를 살펴보자. 그러면 Yule Lads(이)가 여섯 명 있고, 거리에는 집도 여섯 채 있다. 어떤 Yule Lad도 아프지 않다고 가정했을 때, 크리스마스 전 여섯 밤 동안 매일 일어나는 일은 다음과 같다.

• 크리스마스 엿새 전 밤에는 Yule Lad(이)가 $6$번 집의 전구를 끈다.

• 크리스마스 닷새 전 밤에는 Yule Lad(이)가 $5$번 집의 전구를 끈다.

• 크리스마스 나흘 전 밤에는 Yule Lad(이)가 $4$번 집의 전구를 끈다.

• 크리스마스 사흘 전 밤에는 Yule Lad(이)가 $3$번 집의 전구를 끄고, $6$번 집의 전구를 켠다.

• 크리스마스 이틀 전 밤에는 Yule Lad(이)가 $2$번 집과 $6$번 집의 전구를 끄고, $4$번 집의 전구를 켠다.

• 크리스마스 전날 밤에는 Yule Lad(이)가 $1$번 집과 $4$번 집의 전구를 끄고, $2$, $3$, $5$, $6$번 집의 전구를 켠다.

하지만 실제로 일어난 일과 달리, 크리스마스 당일에 $4$번 집의 전구가 꺼져 있다.

반면 크리스마스 나흘 전에 마을에 올 예정이었던 Yule Lad만 아팠다면, 크리스마스 당일에 $1$번 집을 제외한 모든 집의 전구가 켜져 있게 된다. 따라서 정답은 $5$(이)다. 크리스마스 $6$, $5$, $3$, $2$, $1$일 전에 Yule Lads(이)가 마을에 왔다.

채점

제출한 풀이는 여러 부분 과제를 기준으로 채점된다. 각 부분 과제는 여러 테스트 케이스로 구성된다. 부분 과제의 점수를 받으려면 해당 부분 과제에 속한 모든 테스트 케이스를 통과해야 한다.

부분 과제 | 점수 | 제한

1 | 15 | $N \leq 13$

2 | 10 | $N \leq 1000$

3 | 12 | $N \leq 10^5$

4 | 13 | $N \leq 5 \cdot 10^{6}$

5 | 15 | $N \leq 10^{8}$

6 | 14 | $N \leq 10^{10}$

7 | 21 | 추가 제한 없음

입력의 첫 번째 줄에는 양의 정수 $N$ ($1 \leq N \leq 10^{13}$)가 주어진다. 이는 율 라드의 수이자 거리에 있는 집의 수이다.

마을에 온 Yule Lads의 수를 나타내는 정수 하나를 출력한다. $1$번 집을 제외한 모든 집의 전구가 켜지는 경우는 단 하나뿐임이 보장된다.