Strange Sequence#11112

Strange Sequence

1 second
128 megabytes
Easy

From the given number , the following sequence is obtained:

S_0 = n,

S_i = f(S_{i-1}), where i \geq 1

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

f(2214) = 4221 - 1224 = 2997

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

Input

Two integers (0 \leq n \leq 10^9) and (0 \leq k \leq 10^5).

Output

Print the value of S_k.

Examples

Let n = 2214, k = 2. Then:

S_0 = 2214,

S_1 = f(2214) = 4221 - 1224 = 2997

S_2 = f(2997) = 9972 - 2799 = 7173

Example 1

Loading
Loading