To avoid the lady-killer, Elaine decide to set a group number of infrared rays in her dormitory.
The rays have to link several emitters. You must link all the emitters in one group. But you can't link 3 emitters by 3 rays to make a triangle, it will destroy the system.
However, Elaine wanna link as more rays as possible without making any triangle. So she invite you to help her disign this infrared rays system.

This problem contains several cases.
Each case is an integer N (1 < N <= 10^9), indicates the number of emitters.

For each case, you should tell Elaine the maximum number of infrared rays she needs.