Challenge 01: Tidy Cards

After slamming his head against the programming challenges on HackerRank and LeetCode last year, Chad 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, Chad Bill had to move off-campus, which involved relocating many of his prized possessions such as his Birkenstocks, yellow headphones, mini-kanken backpack, 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, Chad Bill decided to count how many cards he had in each deck before and after the move.

As counting cards is a tedious task, Chad 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 real research to do yet⁵, Chad 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 Chad 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 Chad 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 Chad 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 01:

$ cd path/to/cse-34872-su19-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 challenge01               # Create and checkout challenge01 branch

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

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

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

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

# Check code by submitting to dredd using provided script
$ .scripts/submit.py
Submitting challenge01 assignment ...
Submitting challenge01 code ...
  Result Success
   Score 6.00

# Check code by submitting to dredd using curl
$ curl -F source=@challenge01/program.cpp https://dredd.h4x0r.space/code/cse-34872-su19/challenge01
{"score": 6, "result": "Success"}

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

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

Once you have commited your work and pushed it to GitLab, remember to create a merge request.