Stanford has to select a team of dodgeball players from its class of 2013. There are n students in the class and each student is identified by his/her student ID, which is between 1 and n. The coach has to select K players out of these n students for his team. But there is a twist, if among the K dodgeball players, a player's ID number evenly divides another player's ID number, then there is a high chance of them getting into a fight. The coach will do his best to select the K players so that no pair of players among them will want to fight one another. But if the game turns out to be very popular, this becomes impossible. Complete the function dodgeBall to return the minimum size of K at which it becomes impossible to choose a dodgeball team that has no fighting?

Input Format:

One line of text, containing the size of the class of 2013, n

Constraints:

1 <= n <= 5,000,000,000

n is guaranteed to be an even number

Output Format:

The minimum size of K that guarantees the existence of 2 players who fight with each other in any K-sized subset of the class.

Sample Input:

4

Sample Output:

3

Explanation:

If the team = {1,2,3}: 1&2 or 1&3 can fight with each other

If the team = {1,3,4}: 1&3 or 1&4 can fight with each other

If the team = {2,3,4}: 2&4 can fight with each other

If K=2, then the teams {3,4} or {2,3} will have no fights. So 3 is the smallest value of K for which any K-sized team, must include a fighting pair.

Sample Input:

2

Sample Output:

2

Explanation:

The team = {1,2}: 1&2 can fight with each other

I think that the answer is n/2 + 1.

- EPavlova March 23, 2016