Digital River (Shortest And Fastest Solution) This is my first question, so I hope it goes well.

Background:

It's not the rivers that you might be thinking about. The question revolves around the concept of digital rivers. A digital river is a sequence of numbers where the number following n is n plus the sum of its digits.

Explanation:

12345 is followed by 12360 since 1+2+3+4+5=15 and so 12345 + 15 gives
12360. similarly 145 is followed by 155. If the first number of a digital river is M we will call it river M. 

For e.g: River 480 is the sequence beginning {480,492,507,519....}, and river 483 is the sequence beginning {483,498,519,....}. Normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values.

Example:

River 480 meets river 483 at 519. River 480 meets river 507 at 507 and never meets river 481. Every digital river will eventually meet river 1, river 3 or river 9.

Write a program that can determine for a given integer n the value where river n first meets one of these three rivers.

Input

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n (1 &lt;= n &lt;= 16384). A test case with value of 0 for n terminates the input and this test case must not be processed.

Output

For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then on a separate line output the line "first meets river x at y". Here y is the lowest value where river n first meets river x (x = 1 or 3 or 9). If river n meets river x at y for more than one value of x, output the lowest value. Print a blank line between two consecutive test cases.

Test case

Input:

86
12345
0


Output:

Case #1

first meets river 1 at 101

Case #2

first meets river 3 at 12423


Scoring:

The fastest algorithm wins. In case of tie. The one with shorter code will win. 

Thanks to mbomb007 for pointing out my error.                                                                

p.s: I want to have the fastest solution rather than the smallest one.
I also have a solution of mine which is slow. For that look here.

Note:

I will be using this for code testing. And performance checking.
C, 320 294 bytes

Compile with -std=c99

#include&lt;stdio.h&gt;
int s(int i){for(int j=i;j;j/=10)i+=j%10;return i;}int main(){int c=0,i;while(scanf("%d",&amp;i)){c++;if(!i)continue;int j,o[]={1,3,9},p[]={1,3,9};Q:for(j=0;j&lt;3;j++){if(o[j]==i)goto D;else if(o[j]&lt;i){o[j]=s(o[j]);goto Q;}}i=s(i);goto Q;D:printf("Case #%d\n\nfirst meets river %d at %d\n\n",c,p[j],o[j]);}}


Ungolfed:

#include &lt;stdio.h&gt;

int s(int i)
{
    for(int j = i; j; j /= 10)
        i += j % 10;
    return i;
}

int main()
{
    int c = 0, i;
    while(scanf("%d", &amp;i))
    {
        c++;
        if(!i)
            continue;
        int j,o[]={1,3,9},p[]={1,3,9};
        Q: for(j = 0; j &lt; 3; j++)
        {
            if(o[j] == i)
                goto D;
            else if(o[j] &lt; i)
            {
                o[j] = s(o[j]);
                goto Q;
            }
        }
        i = s(i);
        goto Q;
        D: printf("Case #%d\n\nfirst meets river %d at %d\n\n", c, p[j], o[j]);
    }
}


Try it out!

Essentially, the "target" rivers are increased until they're greater than the river we're testing against, and afterwards the test river is increased. This is repeated until the test river is equal to some other river.

I'm not reading parameters from the command line in this program, and I'm not sure if you're supposed to. Now you can pass parameters to STDIN. You can terminate by passing a non-numeric input.

Also darn, beaten by half an hour.