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

设 $a_1, a_2, \cdots$ 是一个整数序列，其首项为 $a_1 = 1$。对于 $n \ge 1$，$a_{n+1}$ 等于 $a_n$ 加上 $a_n$ 的各位数字之和。正因如此，我们将该序列称作“新自描述序列”。 该序列的前几项为 $1, 2, 4, 8, 16, 23, 28, 38, 49, \cdots$，同时我们定义前缀和 $s_n = a_1 + a_2 + \cdots + a_n$。对于给定的正整数 $n$，求 $a_n$ 和 $s_n$。

输入的第一行包含一个整数 $T$（$T \le 32768$），表示测试用例的总数。接下来的 $T$ 行中，每行给出一个整数 $n$（$n \le 10^{17}$）。

对于每组测试用例，首先输出其用例编号。随后，针对给出的 $n$，输出 $a_n$ 和 $s_n$。由于前缀和可能很大，你只需输出 $s_n \bmod 1000000009$。然而，你必须输出 $a_n$ 的精确值。