设 $a_1, a_2, \dots$ 是一个以 $a_1 = 1$ 开头的整数序列。对于 $n \ge 1$，有 $a_{n+1} = a_n + \text{sum\_digits}(a_n)$，其中 $\text{sum\_digits}(a_n)$ 表示 $a_n$ 的各位数字之和。这就是我们将该序列称为“新的自描述序列”的原因。
该序列的前几项为 $1, 2, 4, 8, 16, 23, 28, 38, 49, \dots$，我们同时定义前缀和 $s_n = a_1 + a_2 + \dots + a_n$。对于给定的正整数 $n$，求 $a_n$ 和 $s_n$。
输入格式
输入的第一行包含一个整数 $T$ ($T \le 32768$)，表示测试用例的总数。接下来的 $T$ 行，每行提供一个整数 $n$ ($n \le 10^{17}$)。
输出格式
对于每个测试用例，首先输出其用例编号。然后对于给定的 $n$，输出 $a_n$ 和 $s_n$。由于前缀和可能很大，你只需要输出 $s_n \pmod{1000000009}$。但对于 $a_n$，你需要输出其精确值。
样例
样例输入 1
7 6 66 666 6666 66666 123456789 31415926535897932
样例输出 1
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