BYTESM1  Mystical River
Harry Potter was punished for his impudence by Snape and was sent to the forbidden forest for detention. He has now lost his way amidst the forest. He has come across 3 mystical rivers flowing in his way to the school but he is not sure which river does he have to cross. Alongside each mystical river are stones after every meter with a number written on them. The numbers start with 1, 3 and 9 respectively for the three rivers. The number on a stone is equal to the no. on the previous stone plus the sum of its digits. For example, if one no. is 403 then the next no. is 403+4+0+3=410, the next no. is 410+4+1+0=415 and so on. Harry calls this a ‘stone river’. Harry knows that he has to cross at the stone number which is part of the stone river of the number he remembers. He has to now find the point of intersection of the stone river generated by the no. ‘N’ that he remembers, with the rivers of 1 or 3 or 9. Your task is to find which mystical river intersects the stone river generated by Harry’s number. Also find the point of intersection at which Harry can cross the mystical river. For example, if Harry remembers that he has to cross at the stone number which is part of the stone river of 29 then he has to cross at the stone number 107 which is also in the river of number 1. Stone river of 29: 29,40,44,52,59,73,83,94,107,…. River of 1: 1,2,4,8,16,23,28,38,49,62,70,77,91,101,103,107,…. Both the rivers meet at 107 and hence Harry has to cross at stone number 107. It is possible that the stone river might intersect with more than one of the mystical rivers. In that case, output the least intersection number.
Input
The first line consists of a single integer ‘T’ (1<=T<=50) which is the total number of test cases. Each of the next T lines consist of a single integer ‘N’ (1<=N<=99999999) which is the number that Harry remembers.
Output
A total of T lines, where each line consists of two integers separated by a space. The first integer represents the river out of 1, 3 and 9 which intersects with the stone river of ‘N’. The second integer represents the stone number at which Harry can cross.
Example
Input: 2 29 42 Output: 1 107 3 111
hide comments
sandeep aggrawal:
20111201 17:23:12
can some body help me in this question ???


Paritosh Aggarwal:
20090227 12:41:26
The time limit is a bit lax. Nice question though. 

Srinivas Iyengar:
20090228 10:57:46
Well After the TLE Need to think something better It seems ... Thanks a ton for changing the Time Limit :) Last edit: 20090228 10:57:46 
Added by:  Paritosh Aggarwal 
Date:  20090221 
Time limit:  1.399s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PASGPC PASFPC PERL PHP PIKE PRLGswi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE 
Resource:  British Informatics Olympiad, 1999 