Problem B. Numeric Keypad

# Problem B. Numeric Keypad ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april2/problem/2) ### Problem 鏃堕棿闄愬埗:10000ms 鍗曠偣鏃堕檺:1000ms 鍐呭瓨闄愬埗:256MB ### 鎻忚堪 The numberic keypad on your mobile phone looks like below: ~~~ 1 2 3 4 5 6 7 8 9 0 ~~~ Suppose you are holding your mobile phone with single hand. Your thumb pointsat digit 1. Each time you can 1) press the digit your thumb pointing at, 2)move your thumb right, 3) move your thumb down. Moving your thumb left or upis not allowed. By using the numeric keypad under above constrains, you can produce somenumbers like 177 or 480 while producing other numbers like 590 or 52 isimpossible. Given a number K, find out the maximum number less than or equal to K that canbe produced. ### 杈撳叆 The first line contains an integer T, the number of testcases. Each testcase occupies a single line with an integer K. For 50% of the data, 1 <= K <= 999. For 100% of the data, 1 <= K <= 10500, t <= 20. ### 杈撳嚭 For each testcase output one line, the maximum number less than or equal tothe corresponding K that can be produced. 鏍蜂緥杈撳叆 ~~~ 3 25 83 131 ~~~ 鏍蜂緥杈撳嚭 ~~~ 25 80 129 ~~~