Today at school in a math lesson they are divisible. To demonstrate the properties of divisibility, the teacher wrote down on the board all the integers from 1 to
N into several groups, and if one number is divisible by another, then they necessarily ended up in different groups. For example, if you take N = 10, you get 4 groups.
- First group: 1.
- Second group: 2, 7, 9.
- Third group: 3, 4, 10.
- Fourth group: 5, 6, 8.
You guessed it, since any number is divisible by 1, one group will always consist of only the number 1, but otherwise such a split can be done in various ways. You are required to determine the minimum number of groups into which all numbers from 1 to N can be divided in accordance with the above condition.
The program receives as input one natural number N, not exceeding 10
9, and should output a single number – the desired minimum number of groups.
Examples