题目描述

设 $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$ 的精确值。

7
6
66
666
6666
66666
123456789
31415926535897932

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