Power Deletion Game

Paige and George are playing a game. Paige writes the numbers \(\{1,2,\cdots,n\}\) on a blackboard. In each round, they choose a number \(x\) uniformly at random from those remaining. They then delete every number of the form \(x^k\) (with \(k\) being any positive integer) that is present on the blackboard.

The game continues until the blackboard is empty. Determine the expected number of rounds needed for the game to finish.

An answer is accepted if its absolute error does not exceed \(10^{-4}\).

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq N\), with \(N\) small enough to allow a bitmask dynamic programming solution) representing the numbers written on the board: \(\{1,2,\cdots,n\}\).

outputFormat

Output a single number: the expected number of rounds for the game to finish. The answer is accepted if the absolute error does not exceed \(10^{-4}\).

sample

1

1.0000