Cool Numbers

All submissions for this problem are available.
Consider a positive integer N. Denote its decimal digits by X_{1}, X_{2},..., X_{K}. N is called a Cool Number if you can select at most three (but at least one) of its digits such that the following number is divisible by N:
where S is the sum of the selected digits.
Let LC(N) be the largest Cool Number which is not greater than N, and UC(N) be the smallest Cool Number which is greater than N. So the following inequalities hold
Your task is to find for the given positive integer N the values of LC(N) and UC(N). As you will see from the examples LC(N) and UC(N) exist for every positive integer N.
Consider some examples.
 1458 is a Cool Number since ((1 + 4 + 5 + 8) – (1 + 5))^{1 + 5} = 12^{6} = 2985984 is divisible by 1458. Note that here we select two digits: 1 and 5.
 All numbers of the form 10^{n} (n = 0, 1, 2, ...) are Cool. Indeed, if we select just one digit 1 (the first digit of 10^{n}) in the definition of Cool Number we obtain the number (1 + 0 + ... + 0 – 1)^{1} = 0^{1} = 0 and it is divisible by 10^{n} (recall that 0 is divisible by every positive integer). Now consider some positive integer N of n digits. Then, clearly, 10^{n1} ≤ N < 10^{n} where both 10^{n1} and 10^{n} are Cool Numbers. Hence LC(N) and UC(N) always exist and, moreover, LC(N) ≥ 10^{n1} and UC(N) ≤ 10^{n}.
Input
The first line of the input file contains an integer T, the number of test cases. Each of the following T lines contains a positive integer N.
Output
For each test case output on a single line values of LC(N) and UC(N) separated by a single space.
Constraints
1 ≤ T ≤ 100000
1 ≤ N ≤ 10^{1000}
The total number of digits in all numbers N in the input file does not exceed 4000000.
Example
Input: 4 2 999 1459 18898888 Output: 2 3 999 1000 1458 1460 18895680 18900000
Explanation
Case 1. The number 2 is the largest integer which is not greater than N = 2, the number 3 is the smallest integer which is greater than N = 2, and they both are Cool Numbers, which can be shown similar to the case of 10^{n} in the example above.
Case 2. It is very similar to the first test case and we already know that 1000 is a Cool Number. So we just have to show that 999 is a Cool number. But it is clear, since we can select all the three digits so ((9 + 9 + 9) – (9 + 9 + 9))^{9 + 9 + 9} = 0^{27} = 0 which is divisible by 999.
Unfortunately, we can't provide you with the explanation of the third and the fourth test cases. You should figure it out by yourself. Please, don't ask about this in comments.
Warning!
There are large input and output files in this problem. Make sure you use fast enough I/O methods.
Author:  iscsi 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/COOLNUM 
Tags  hard, iscsi , june12, primefactor 
Date Added:  18042012 
Time Limit:  1.34426 sec 
Source Limit:  30000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions