New Self-describing Sequence
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
Let $a_1, a_2$,... be an integer sequence beginning with $a_1$ = 1. For n ¡Ý 1, $a_n$+1 is the sum of an and the sum of digits of $a_n$. That¡¯s why we name the sequence a new Self-describing sequence.
The sequence starts with 1, 2, 4, 8, 16, 23, 28, 38, 49, ... and we also define the prefix sum $s_n = a_1 + a_2 + ... + a_n$.
For given positive integer n, find $a_n$ and $s_n$.
The sequence starts with 1, 2, 4, 8, 16, 23, 28, 38, 49, ... and we also define the prefix sum $s_n = a_1 + a_2 + ... + a_n$.
For given positive integer n, find $a_n$ and $s_n$.
Input
The first line of input consists an integer T (T ¡Ü 32768), indicating the total number of test cases. Each of the following T lines provides an integer n (n ¡Ü 10^17).
Output
For each test case output its case label first. Then for given n, output $a_n$ and $s_n$. Since the prefix sum is large,you only need to output $s_n$ mod 1000000009. However you should output $a_n$ as its exact value.
Sample Input
7 6 66 666 6666 66666 123456789 31415926535897932
Sample Output
Case #1: 23 54 Case #2: 752 20862 Case #3: 10949 3407733 Case #4: 136193 441127485 Case #5: 1698899 717710112 Case #6: 5061289531 990040993 Case #7: 2508156610654066874 660828136