Shape Number

In computer vision, a chain code is a sequence of numbers representing directions taken while following the contour of an object. For example, the figure below shows a contour represented by the chain code 22234446466001207560 (starting at the upper-left corner).

Two chain codes may represent the same shape when the shape has been rotated, or when a different starting point is chosen along the contour. To normalize for rotation, we compute the first difference of the chain code: between each pair of consecutive elements we count the number of counterclockwise direction changes, i.e. (next - current) mod 8 (the last element is considered consecutive with the first). For the code above, the first difference is

00110026202011676122

Finally, to normalize for the starting point, we consider all cyclic rotations of the first difference and choose the lexicographically smallest one. The resulting code is called the shape number.

00110026202011676122
01100262020116761220
11002620201167612200
...
20011002620201167612

In this case, 00110026202011676122 is the shape number of the shape above.

The input consists of several cases, one per line, read until end of input. Each line is the chain code of one shape. The length of a chain code is at most $300{,}000$, and every digit is between $0$ and $7$ inclusive. The contour may intersect itself and need not return to its starting point.

For each case, print the resulting shape number on its own line.