Night king is marching with an army of the dead. The Night King has $N$ deads in his army and they are labelled from $1$ to $N$. Jon Snow is trying hard to stop Night King to cross the wall and destroy Westeros. Jon figures out that killing a walker leads to the disintegration of some of his associated wights.

If Jon kills the $kth$ dead all the dead with a label which divides $k$ will be disintegrated. For $N = 123456789$, what is the minimum number of kills required to clear the army?