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 independent1. Instead, he opted to take his talents to the monastery academia, where he could fulfill his live-long ambition of being a graduate teaching assistant2.

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 cards3. To ensure he didn't lose any cards in the process of moving from Duncan4 to his new apartment house5, 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 yet5, 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``````

This programming challenge is based on Problem B. Tidy Numbers from the 2017 Qualification Round of Google Code Jam.

## Submission

``````\$ cd path/to/cse-30872-fa19-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 commit -m "challenge00: done"         # Commit your changes

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

#### Programming Languages

Note, dredd supports C, C++, Python, Java, Go, Node, Ruby, Perl6, and Guile. You may use any of those languages, just be sure to name your source file `program.\$EXTENSION` where `\$EXTENSION` is the appropriate file extension for your chosen language (e.g. `py` for Python).

If you wish to try out another language, please let the instructor know and support can be added to dredd.

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 challenge00 assignment ...

Submitting challenge00 program.py ...
Result Success
Score 6.00
Time 0.02

# Check code by submitting to dredd using curl
\$ curl -F source=@challenge00/program.py https://dredd.h4x0r.space/code/cse-30872-fa19/challenge00
{"score": 6, "result": "Success", "time": 0.0322721004486084}``````

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

Score Description Notes
6.0 Success Program has successfully passed all test cases within the provided time limit.
5.0 Output Format Error Output appears mostly correct, except the formatting is wrong (usually a whitespace or spelling error).
4.0 Time Limit Exceeded Program did not terminate within the provided time limit (10 seconds).
3.0 Wrong Answer Output does not match test cases.
2.0 Execution Error Program did not terminate successfully (usually a segmentation fault or exception)
1.0 Compilation Error Program failed to compile (usually a syntax error)

#### Test Cases

Note, dredd contains additional test cases beyond that which is show in the examples above. This means that even if you pass on the input above, you are not guaranteed to pass the dredd test if you do not handle additional situations.

This means you should consider what the possible edge cases are and how to handle them. Feel free to create your own input and output test files and use them to verify your program:

``````# 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. Refer to the Reading 00 TA List to determine your corresponding TA for the merge request.

1. Student loans 4 lyfe. J/K. Not really. Maybe?

2. He was the head TA for the class that shall not be named.

3. He is always looking for people to play with!

4. The dorm not the "student" center which is sometimes closed to students.

5. Cost of living in South Bend so good...