翻转数相乘

题目描述

假设一个 $n$ 位数为 $a_1a_2a_3\cdots a_n$，其中 $a_i$ 是这个数第 $i$ 位上的数字，并且这个 $n$ 位数不是每一位都相同的数字，例如不是 $2222$ 或类似数字。

如果存在一个整数 $x$，且 $1<x<10$，使得：

$$a_1a_2a_3\cdots a_n \times x = a_na_{n-1}a_{n-2}\cdots a_1$$

求所有满足条件的 $x$。其中 $a_1$ 和 $a_n$ 不能为 $0$。

如果 $x$ 无解，则输出 $0$；如果有多个 $x$，则从小到大输出所有 $x$，每个数占一行。

例如：一个 $5$ 位数 $ABCDE$，满足：

$$ABCDE \times ? = EDCBA$$

其中 $A,B,C,D,E$ 是一位整数，$ABCDE$ 和 $EDCBA$ 都是五位数，求符合等式的乘数。

输入格式

输入一个整数 $n$，表示要求解的位数。

输出格式

输出所有可能的乘数，并按照从小到大排列，每个数占一行。

如果不存在合法乘数，输出一行 0。

数据范围

$2 \le n \le 8$，$1<x<10$。

输入输出样例

输入 #1

6

输出 #1

4
9