P17074 [ICPC 2017 Shenyang R] New Self-describing Sequence

Let $a_1, a_2, \cdots$ be an integer sequence beginning with $a_1 = 1$. For $n \ge 1$, $a_{n+1}$ is the sum of $a_n$ 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, \cdots$ and we also define the prefix sum $s_n = a_1 + a_2 + \cdots + a_n$. For given positive integer $n$, find $a_n$ and $s_n$.

The first line of input consists an integer $T$ ($T \le 32768$), indicating the total number of test cases. Each of the following $T$ lines provides an integer $n$ ($n \le 10^{17}$).

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 \bmod 1000000009$. However you should output $a_n$ as its exact value.