ININT - Incrementing The Integer

no tags 

Starting from the number '1', every time you can choose a digit from the current number and add it to the number itself. 23, for example, could be changed into 25 or 26. To get 100, using the above scheme, paths A and B are both possible. A requires 21 steps, but B needs only 17 (which is also the minimum)

A. 1-2-4-8-16-17-18-19-20-22-24-28-36-39-48-56-62-68-76-83-91-100
B. 1-2-4-8-16-17-24-28-36-39-48-56-62-68-76-83-91-100

C is another 17 step solution for 100.

C. 1-2-4-8-16-22-24-28-36-39-48-56-62-68-76-83-91-100

Now, you are given several numbers, for each number, print the minimum steps S and number of solutions T. As T could be quite large, you should print T%1000000007 instead.

Input

Each line of input contains a integer K as a test case. Input ends with End Of File.

Output

For each test case print the minimum steps and solutions in a single line. If it's impossible to get the number, print "IMPOSSIBLE" instead. ( without the quotes ).

Example

Input:
16
100
87

Output:
4 1
17 2
IMPOSSIBLE

Constraints and Limits

Number of test cases ≤ 100, 1 ≤ K ≤ 10^9.


hide comments
nadstratosfer: 2017-12-21 16:54:59

In my experience, problems where the fastest C solution exceeds 0.04s are not solvable in Python unless the TL is relaxed (eg. this one probably isn't).

offero: 2017-12-20 02:26:49

Does python even run in the provided time limit?

kayacan: 2014-02-25 11:16:13

what is the limit K


Added by:Ajay Somani
Date:2008-02-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:CodeCraft 08, Problem Setter: Jin Bin