The Four-Digit Black Hole Number

Problem Description

The black hole number (also called trap number, or the "Kaprekar problem") is a class of numbers with a peculiar transformation property. Any four-digit number whose digits are not all the same will, after a finite number of "rearrange-and-subtract" operations, always reach $6174$. The resulting $6174$ is the four-digit black hole number. ($495$ is the three-digit black hole number.) The so-called "rearrange-and-subtract" operation means: subtract the smallest number formed by rearranging the digits from the largest number formed by rearranging the digits.

For example, for the four-digit number $1234$:

• 1st operation: $4321 - 1234 = 3087$;
• 2nd operation: $8730 - 378 = 8352$ (note: $0378$ is written as $378$);
• 3rd operation: $8532 - 2358 = 6174$;

after which it stays at the black hole number $6174$. If the four digits of the number are all the same, one operation yields $0$.

Given any four-digit number, write a program that prints the rearrange-and-subtract process.

Input Format

A four-digit number given on one line.

Output Format

Print the rearrange-and-subtract process in the following format:

index: largestRearrangedNumber - smallestRearrangedNumber = difference

The index starts from $1$ and continues until $6174$ appears on the right side of the equals sign.

Sample Input

1234

Sample Output

1: 4321 - 1234 = 3087
2: 8730 - 378 = 8352
3: 8532 - 2358 = 6174

Sample Explanation

The input four-digit number is $1234$. First rearrange the digits $1,2,3,4$ to get the largest number $4321$ and the smallest number $1234$, subtract to get $3087$. Then repeat the operation on $3087$: rearrange to get the largest number $8730$ and the smallest number $0378$ (written as $378$), subtract to get $8352$. Continue: rearrange to get largest $8532$ and smallest $2358$, subtract to get $6174$, and the process ends.

Constraints

The input four-digit number satisfies $1000 \le n \le 9999$.