题目描述
L发明了一个加密算法，如果有一个数字X，他取X^2X
2
的最后9位数字，不足在前面补0。现在你拿到了加密的数字串，想破解这个密码。请你输出所有的可能数字（从小到大输出 ）原数字大小 < 10^9<10
9
保证答案的个数不超过 40004000 个。
输入格式
输入一行，一个长度为 9 的数，前面可以是 0。
输出格式
从小到大输出所有可能的数，每个数一行，如果那个数不足 9 位，就在前面输出 0。
样例
输入数据 1
987654321
输出数据 1
111111111
119357639
380642361
388888889
611111111
619357639
880642361
888888889
数据规模与约定