Problem Description

Cyy has m kinds of characters,numbered from 1 to m,and the cost of using an i-th character is i.He wants to use these characters to construct N nonempty strings.Every string can not be a prefix of another string.Now he wants to know what the minimum cost is.

Input

There are multiple test cases, no more than 1000 cases.
For each case contains two integers n and m on a line.$(1\leq n\leq {10}^{9},2\leq m \leq {10}^{9})$

Output

For each test case,output minimum cost in a line.

1 2
3 2
5 2
1000 100000

1
7
17
10464