Shape Number#2752
In computer vision, a chain code is a sequence of numbers representing directions when following the contour of an object. For example, the following figure shows the contour represented by the chain code (starting at the upper-left corner).
Two chain codes may represent the same shape if the shape has been rotated or if a different starting point is chosen for the contour. To normalize the code for rotation, we can compute the first difference of the chain code instead. The first difference is obtained by counting the number of direction changes in the counterclockwise direction between consecutive elements in the chain code (the last element is consecutive with the first one). In the above code, the first difference is
Finally, to normalize for the starting point, we consider all cyclic rotations of the first difference and choose among them the lexicographically smallest such code. The resulting code is called the shape number.
In this case, is the shape number of the shape above.
The input consists of a number of cases. The input for each case is given in one line, consisting of a chain code of a shape. The length of the chain code is at most , and all digits in the code are between and inclusive. The contour may intersect itself and need not trace back to the starting point.
For each case, print the resulting shape number after the normalizations discussed above are performed.
Example 1