SILVER - Cut the Silver Bar

A creditor wants a daily payment during n days from a poor miner in debt. Since the miner can not pay his daily obligation, he has negotiated with the creditor an alternative way, convenient for both parties, to pay his debt: the miner will give an equivalent of a 1µ (= 0.001mm) long piece of a silver bar as a guarantee towards the debt. The silver bar owned by the poor miner is initially nµ units long.

By the end of n days the miner would not have any more silver to give and the creditor would have received an amount of silver equivalent to that of the silver bar initially owned by the miner. By then, the miner expected to have enough money to pay the debt at the next day so that he would have back all his silver.

With this negotiation in mind, the miner has realized that it was not necessary to cut exactly 1µ silver piece from the bar everyday. For instance, at the third day he could give the creditor a 3µ silver piece, taking back the equivalent of a 2µ silver piece which the creditor should already have.

Since cutting the bar was rather laborious and time consuming, the miner wanted to mini-mize the number of cuts he needed to perform on his silver bar in order to make the daily silver deposits during the n days. Could you help him?

Input

Input consists of several cases, each one defined by a line containing a positive integer number n (representing the length in micras of the silver bar and the number of days of the amortization period). You may assume that 0 < n < 20000. The end of the input is recognized by a line with 0.

Output

For each given case, output one line with a single number: the minimum number of cuts in which to cut a silver bar of length nµ to guarantee the debt during n days.

Example

Input:
1
5
3
0

Output: 0
2
1

Added by:John Mario
Date:2011-04-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:XXIV Colombian Programming Contest ACIS REDIS 2010 - ACM ICPC

hide comments
2017-04-26 09:54:18 Shubham Dash
My 50th AC!!! O(1) solution
2017-04-07 22:01:38 ANKIT JAIN
oh !! lovely question
2017-03-22 18:02:49
Like CC long challenge 1st problem(very easy).Don't know how guys did in O(1) ..mine was O(n).
2017-03-16 14:32:15
easier than what u think :P
2017-03-04 15:41:19
The statement is complicated than the logic itself!
2017-02-26 20:08:24
AC in a go bitch!
2017-01-24 17:48:48
Nice Problem , Everyone should do it , never go by comments , they just deviate you from original thinking , Think critically and no problem is bad and no problem is hard, May i ask how are you able to do it in single line ,?
2017-01-14 18:46:26
@madhavgaba
it is very basic... you dont need pen paper :D
2016-12-23 16:48:59
@nikhilkala shut up!

Last edit: 2017-01-19 14:44:34
2016-11-27 17:13:39
It says wrong solution to me even when I'm getting the exact same output on ide.

Last edit: 2016-11-27 17:14:39
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.