BRTREE - Bread Tree


Breadtree is a kind of tree that produces bread. At its first year, a breadtree is only a node with a bread of weight 0 on this node which is also called zeronode. Every year after that, the weight of bread on each node of the tree will increase by 1, and another branch with a zeronode will grow at the end of each node. However, there is a limit of branches on each node. That is, when the number of branches of a node reaches the limit, there won't be any more branches, but the weight of its bread will still increase. What's more, a breadtree remains unchanged when the total weight of bread is larger than 1234567890.

Input

There are two integers N and K on each line. N is a positive integer fit in signed 32-bit integer. K is a non-negative integer fit in signed 32-bit integer. An N equals to 0 signals the end of input, which should not be processed.

Output

Output the total weight of bread on a breadtree with branches limit K in the N-th year in a line for each case.

Example

Input:
10000 0
101 1
10 2
1221 128
0 0


Output:
9999
5050
221
2147483647


hide comments
Luka: 2014-01-02 08:22:00

getting WA. @problem setter: Please check

Moron: 2012-11-16 18:44:05

any other test case please

Gurpreet Singh: 2012-06-17 07:26:13

any test case(s) plzzz...
Edit : gotcha...

Last edit: 2012-06-17 09:30:43
Bharath Reddy: 2011-12-27 06:15:45

Nice problem :)

Last edit: 2011-12-27 07:26:03

Added by:Race with time
Date:2009-01-24
Time limit:0.860s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ZOJ Monthly, January 2009 - A