405072: GYM101775 F Good Number

Given a positive integer M that consists of k digits in decimal notation without leading zeros, a 'digit rotation' of M means a number that is generated by swapping the first j digits and the rest (k - j) digits on M, for any j (0 ≤ j < k). For example, both 231 and 312 are digit rotations of 123, and neither 321 nor 132 is.

A positive integer G is a good number if any digit rotation of G does not exceed G.

Given a positive integer N, return the largest good number that does not exceed N.

The first line of the input gives the number of test cases, T. T test cases follow.

Each line contains an integer N which is represented in decimal notation.

• 1 ≤ T ≤ 500.
• 1 ≤ N ≤ 10^1000000.
• .

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the largest good number that does not exceed N.

4
110
10010
45363
8394634

Case #1: 110
Case #2: 10000
Case #3: 44444
Case #4: 8383837

In the first sample case, 110 is a good number since all the digit rotations of it 101 and 011 are smaller than 110.

In the second sample case, 10010 itself is not a good number because one of the digit rotations 10100 is larger than 10010. 10001 to 10009 either, since 10001's rotation is 11000, 10009's rotation is 91000, similar for 10002 to 10008. Therefore, 10000 is the largest good number.