The Yule Lads' Visit

Icelandic children are very fortunate. In a small town in Iceland, there are N houses numbered from 1 to N, and initially, every house is decorated with Christmas lights that are all turned on. The town also has N Santa Clauses called the Yule Lads. On the K-th night before Christmas, a Yule Lad (if healthy) visits the town. This particular Yule Lad adores the number K and will only visit houses whose numbers are divisible by K. In addition, each visiting Yule Lad mischievously toggles the state of the Christmas lights in the houses he visits (i.e. if a light is on, it turns off, and vice versa).

However, some of the Yule Lads fall ill and do not make the trip. As a result, on Christmas Day, all houses except the first one have their lights turned on.

Your task is to determine how many Yule Lads actually visited the town given that:

Initially, every house's light is on. When a Yule Lad visits, he toggles the light in every house whose number is divisible by his corresponding night number. Hence, the final state of a house is determined by the parity (even or odd) of the total number of toggles it experiences.

Let \(S\subseteq\{1,2,\dots,N\}\) be the set of nights on which the Yule Lads visited. Then, for every house numbered \(i\), the number of times its light is toggled is given by:

[ T(i)=\sum_{\substack{k\in S \ k\mid i}}1. ]

The conditions on the final state of the lights are as follows:

[ \begin{cases} T(1)\equiv 1\pmod{2}, &\text{(house 1 is off)}\ T(i)\equiv 0\pmod{2}, &\text{for all } i\ge2 ; (\text{houses }2\text{ to }N \text{ are on}). \end{cases} ]

Since every house i ≥ 2 always gets toggled once by the Yule Lad corresponding to night 1 (because 1 divides every number) and must end up even, the remaining toggles must sum to an odd number. Define \(X(i)\) for \(i\ge2\) as an indicator that the Yule Lad on the i-th night visited (with \(X(i)=1\) if he visited and 0 otherwise). Then for every \(i\ge2\), we have:

[ X(i)=1+\sum_{\substack{d\mid i\2\le d<i}}X(d)\pmod{2}. ]

The final answer is given by counting the total number of visiting Yule Lads:

[ \text{Answer}=1+\sum_{i=2}^{N}X(i), ]

where the constant 1 comes from the Yule Lad on night 1 who always visits.

inputFormat

A single integer \(N\) representing the number of houses and the total number of potential Yule Lads.

outputFormat

A single integer indicating the number of Yule Lads that visited the town.

sample

1

1