Reverse Engineering

It's a life of crime for you! You and your friends just broke into Bonython Bank, and now, it's time to open their safe containing a million Leetcoins!

As the tech guru, you know find the code for the safe. Given its 4-digit "seed", ~S~, you must repeat the following operation ~N~ times:

• Let ~S_M~ be the number you get after rearranging the digits of ~S~ in descending order.

• Let ~S_m~ be the number you get after rearranging the digits of ~S~ in ascending order.

• Set ~S = abs(S_M - S_m)~.

• Pad ~S~ with zeros, if necessary. For example, 11 -> 0011.

The final value of ~S~ will be the code for the safe.

Quick, the police will get to your location in no time! What is the safe's code?

Input

The first line of each test case contains a 4-digit integer ~S~, the starting value for the operations.

The second line contains an integer ~N~ (~1 \leq N \leq 10^{12}~), the number of times you need to perform the operation.

Output

For each test case, output the code for the safe.

Example

Input

2413
2

Output

8352

We need to do the operation twice.

Operation 1:

• ~S_M = 4321, S_m = 1234~.
• ~S = abs(1234 - 4321) = 3087~

Operation 2:

• ~S_M = 8730, S_m = 0378~.
• ~S = abs(8730 - 0378) = 8352~

The final value of ~S~ is 8352, so the safe's code is 8352.

Example

Input

1111
100

Output

0000

We need to do the operation 100 times.

Operation 1:

• ~S_M = 1111, S_m = 1111~.
• ~S = abs(1111 - 1111) = 0000~

All future operations will make ~S = 0000~, so we know that the safe's code is 0.