Challenge 00: Tidy Cards

After slamming his head against the programming challenges on HackerRank and LeetCode last year, Vector Bill decided that he didn't really want to make money or be financially independent¹. Instead, he opted to take his talents to the monastery academia, where he could fulfill his live-long ambition of being a graduate teaching assistant².

Since he is now a graduate student, Vector Bill had to move off-campus, which involved relocating many of his prized possessions such as his Birkenstocks, yellow headphones, and of course, his Magic The Gathering cards³. To ensure he didn't lose any cards in the process of moving from Duncan⁴ to his new apartment, Vector Bill decided to count how many cards he had in each deck before and after the move.

As counting cards is a tedious task, Vector Bill's mind began to wander and he noticed that some numbers, 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. He really liked this phenomenon and decided to call these numbers tidy. Numbers that do not have this property, like 20, 321, 495 and 999990, are considered not tidy.

Because he doesn't quite have any research to do yet, Vector Bill wonders if there are N cards in a deck, what was the last tidy number he counted?

You are to write a program that helps Vector Bill solve this problem.

Input

The first line of standard input gives the number of test cases, T. T lines follow. Each subsequent line of input describes a test case with a single integer N where 0 <= N <= 1000, which is the total number of cards in that deck as counted by Vector Bill.

Here is an example input:

3
132
1000
7

Output

For each test case, output to standard output one line containing Deck #x: y, where x is the test case number (starting from 1) and y is the last tidy number encountered by Vector Bill.

Here is the output given the example input above:

Deck #1: 129
Deck #2: 999
Deck #3: 7

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge00               # Create and checkout challenge00 branch

$ $EDITOR challenge00/program.cpp           # Edit your code

$ git add challenge00/program.cpp           # Stage your changes
$ git commit -m "challenge00: done"         # Commit your changes

$ git push -u origin challenge00            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge00 assignment ...
Submitting challenge00 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge00/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge00
{"score": 6, "result": "Success"}

The score returned from dredd will be one of the following:

$ ./program < input.txt | diff -u - output.txt

Once you have commited your work and pushed it to GitLab, remember to create a merge request. Refer to the Reading 00 TA List to determine your corresponding TA for the merge request.