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, 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

Google Code Jam

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

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

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 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:

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.


  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. I guess downloading memes is considered research?