Strange Sequence

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

S[0] = n,

S[i] = f(S[i-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 S[k].

Input

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

Output

Print the value of S[k].

Example

Let n = 2214, k = 2. Then:

A[0] = 2214,

A[1] = f(2214) = 4221 − 1224 = 2997

A[2] = f(2997) = 9972 − 2799 = 7173

Examples