Smart TT across the maze safety, she met the big boss! Boss used his power again, then many pillars Drilled out from ground, that hurt TT's army seriously. TT was very angry, luckily, TT also owns some ability. the pillar's height was different, every time TT could choose one or some pillars to destroy, she can cut the same height, but she can't cut more than a pillar's height, that means, if the pillar is 1 2 3 4 5 6, TT could choose 4 5 6, each cut 2(become 2 3 4)or 4(become 0 1 2), but she can't cut 5, because 4 can't cut 5, 0 means this pillar was destroyed. Because her limited power, please calculate the minimun times to destroy all the pillars.

There are many cases. Each case with a integer N(1 <= N <= 2^32), means 1 to N pillars, the ith pillar's height is i.

for each case, output the minimun times to destroy all the pillars.