Tidy Numbers

/* Programmer     : Dhruv Patel
*  Problem Name   : Tidy Numbers
*  Used In        : Google
*  Used As        : Kickstart
*  Problem        :
*                
*                   Tatiana likes to keep things tidy. Her toys are sorted from smallest to largest, her pencils are sorted from 
*                   shortest to longest and her computers from oldest to newest. One day, when practicing her counting skills, she
*                   noticed that some integers, when written in base 10 with no leading zeroes, have their digits sorted in
*                   non-decreasing order. Some examples of this are 8, 123, 555, and 224488. She decided to call these numbers tidy. 
*                   Numbers that do not have this property, like 20, 321, 495 and 999990, are not tidy.
*                   She just finished counting all positive integers in ascending order from 1 to N. What was the last tidy number 
*                   she counted?
*
*  Input           :
*                   The first line of the input gives the number of test cases, T. T lines follow. Each line describes a test case 
*                   with a single integer N, the last number counted by Tatiana.
*
*  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 last tidy number counted by Tatiana.
*  Limits
*                   1 ≤ T ≤ 100.
*                   Small dataset
*
*                   1 ≤ N ≤ 1000.
*                   Large dataset
*
*                   1 ≤ N ≤ 1018.
*  Input                                             Output
*  4                                                 
*  132                                               Case #1: 129
*  1000                                              Case #2: 999
*  7                                                 Case #3: 7
*  111111111111111110                                Case #4: 99999999999999999
*
*  Thoughts       =>
*                   The brute force solution will be to convert each number to string array and 
*                   for a slight optmization we go in backward positon.If we found a tidy number
*                   then simply return it.
*                   The solution is only good to go for small dataset and for larger dataset will
*                   post another senseful solution.
*/

public class Main {
    public static int lastTidyNumber(int number) {
        for (int x = number; x >= 1; x++) {
            char test[] = String.valueOf(x).toCharArray();
            if (test.length == 1) {
                return x;
            } else {
                boolean flag = false;
                for (int i = 0; i < test.length - 1; i++) {
                    if (test[i + 1] >= test[i]) {
                        flag = true;
                    } else {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    return x;
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        while (--T >= 0) {
            System.out.println(lastTidyNumber(input.nextInt()));
        }
    }
}