During, the meeting held to organize a competition in Memory strength, One of

the attendant suggested an idea that was accepted by almost all the organizers.

First, The competition is held such that all competitors oppose each other and

the winner is the one who got the highest score.

At the begin of the competition a sequence of pictures are shown to all the

competitors where their task, during every match, is to arrange the pictures

in front of him/her as quickly as possible in the same order he had seen in

the show.

Let's return to our suggestion, One of the Organizers suggested to put the

pictures in order where each two pictures where shown consecutively in the

show aren't beside each other. Also he suggested that, for each one, along

the competition, isn't allowed to try to put in order the same arrangement of

the pictures he had tried to do that with before.

In order not to help any competitor to remember easily.

Then, he needed to calculate the minimum number of pictures that can be

in the sequence that allow organizing the competition.

Hint:

      All competitors will face each other one through out the competition.

----------------------------------------------

 
Task

 

write a program th reads the number of the competitors and calculate the

minimum number of elements needed in the sequence, that can be arranged,

where no two pictures that where originally next to each other are next to

each other, M times.

M is calculated, such that no one is allowed to try to arrange the same

 sequence more than once, along the competition.

Input

N (number of the competitors), where 1 < N ≤ 10³⁰⁹ 


Output

 
The minimum number of elements needed in the sequence that will be

shown to all the competitors.

INPUT:
5

OUTPUT:
5

Explanation:

   M (minimum number of available arrangements needed) will be 5, in this case,

also a sequence of length 5 can allow 14 unique arrangements.

+ For 5 competitors there are 10 matches (4.0*5.0/2.0)

Notice that each arrangement can be used for more than one match, but one time for each player at maximum.

Hint:
4 can not b the right answer, as with a sequence of length 4, the number of

available arrangements is 2 only - less than needed -.

INPUT: 

89

OUTPUT:

6

Number of test-cases is 52.