From the given number n, the following sequence S is obtained:

S0 = n,

Si = f(Si-1), i ≥ 1

Here f(x) is equal to the difference between the numbers obtained by rearranging the digits of the number x in descending and ascending order. For example:

f(2214) = 4221 − 1224 = 2997

Note that leading zeros are not counted. Find the value of Sk.

Input

Two integers n (0 ≤ n ≤ 109) and k (0 ≤ k ≤ 105).

Output

Print the value of Sk.

Example

Let n = 2214, k = 2. Then:

A0 = 2214,

A1 = f(2214) = 4221 − 1224 = 2997

A2 = f(2997) = 9972 − 2799 = 7173