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.
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.
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.
## Input
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 ≤ 101000000. .
## Output
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.
[samples]
## Note
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.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n, m, q \in \mathbb{Z} $ denote the number of rows, columns, and queries, respectively.
- Let $ G \in \mathbb{Z}^{n \times m} $ be the grid, where $ G[x][y] \in [1, 500] $ for $ x \in \{1, \dots, n\} $, $ y \in \{1, \dots, m\} $.
- Let $ Q = \{(a_k, b_k, c_k, d_k) \mid k \in \{1, \dots, q\}\} $ be the set of queries, where each query defines a submatrix:
$$
S_k = \{ G[x][y] \mid a_k \le x \le c_k,\ b_k \le y \le d_k \}
$$
**Constraints**
1. $ 1 \le T \le 100 $
2. $ 1 \le n, m \le 100 $, $ 1 \le q \le 10^5 $
3. $ 1 \le G[x][y] \le 500 $
4. $ 1 \le a_k \le c_k \le n $, $ 1 \le b_k \le d_k \le m $
5. $ \sum_{\text{test cases}} n \times m \le 3 \times 10^5 $
6. $ \sum_{\text{test cases}} q \le 10^6 $
**Objective**
For each query $ k $, let $ S_k $ be the multiset of values in the submatrix. Sort $ S_k $ in non-decreasing order. Let $ L = |S_k| $.
The median is the element at position $ \left\lfloor \frac{L-1}{2} \right\rfloor $ (0-indexed) in the sorted list.
Output the median for each query.