SILVER - Cut the Silver Bar

no tags 

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

hide comments
prafulla_1503: 2020-05-31 16:10:09

good question...everyone should solve it.

harry_shit: 2019-06-04 14:45:55

advice:go easy on this,don't think too hard

markaman: 2018-12-31 15:06:18

Classroom riddle
Btw 100th on spoj

Last edit: 2018-12-31 15:06:52
csasi: 2018-09-26 17:03:01

Smallest length of code in c++, after hello world or an addition problem.

shashankpathak: 2018-09-24 19:12:22

What is this question statement is not clear.Please if anyone can clarify it

richardks3647: 2018-07-21 07:03:17

AC in one go

ameyanator: 2018-01-23 20:26:12

Ohh lol. When I'd thought of the greedy i was like cmon that's too simple. Anyways coded it and submitted and viola! AC :')

vijayrit: 2017-12-18 15:30:58

just look out for the pattern.

ab_hi_shek111: 2017-09-09 11:44:52

My 100th :)

ace_of_spades: 2017-08-05 14:21:21

awesome question!


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