描述

一个正整数序列是回文序列，如果它从前读和从后读都是一样的。例如：

$23$ $11$ $15$ $1$ $37$ $37$ $1$ $15$ $11$ $23$

$1$ $1$ $2$ $3$ $4$ $7$ $7$ $10$ $7$ $7$ $4$ $3$ $2$ $1$ 1$

如果一个回文序列在中间值之前不下降，而从中间到末尾（由于序列是回文的）不再上升，那么这个序列就是单峰回文序列。例如，第一条示例序列不是单峰回文序列，而第二条示例序列是。

如果一个单峰回文序列的整数和为$N$，那么它就是整数$N$的单峰回文分解。例如，前几个整数的所有单峰回文分解如下所示：

$1: (1)$

$2: (2), (1 1)$

$3: (3), (1 1 1)$

$4: (4), (1 2 1), (2 2), (1 1 1 1)$

$5: (5), (1 3 1), (1 1 1 1 1)$

$6: (6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3), (1 2 2 1), (1 1 1 1 1 1)$

$7: (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)$

$8: (8), (1 6 1), (2 4 2), (1 1 4 1 1), (1 2 2 2 1), (1 1 1 2 1 1 1), (4 4), (1 3 3 1), (2 2 2 2), (1 1 2 2 1 1), (1 1 1 1 1 1 1 1)$

编写程序，计算一个整数的单峰回文分解数目。

输入

输入由若干个正整数构成，每个数字占一行，最后一个数字为$0$（零），表示输入结束。

输出

对于每个输入值（除最后一个外），输出该值和它的单峰回文分解的数量。每个输出值单独占一行，格式如下所示。

2
3
4
5
6
7
8
10
23
24
131
213
92
0

2 2
3 2
4 4
5 3
6 7
7 5
8 11
10 17
23 104
24 199
131 5010688
213 1055852590
92 331143

来源

Greater New York 2002