#656. 「NOIP1999」回文数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Payphone_X

题目描述

若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其称之为回文数。

例如:给定一个 10 进制数 56 ,将 56 65 (即把 56 从右向左读),得到 121 是一个回文数。

又如,对于 10 进制数 87 ,可以做以下四次变换得到回文数:

  1. 87+78= 165

  2. 165+561= 726

  3. 726+627=1353

  4. 1353+3531=4884

在这里的一步是指进行了一次 n 进制的加法,上例最少用了 4 步得到回文数 4884

现在请你写一个程序,对于给出的 n 进制 m .求最少经过几步可以得到回文数。

特别地,如果在 30 步以内(包含 30 步)不可能得到回文数,则输出Impossible

输入格式

输入包括一行,包括两个整数 n m

输出格式

输出包括一行,表示最少步数。

特别地,如果 30 步以内得不到回文数,则输出Impossible

样例

样例输入 1

9 87

样例输出 1

6

数据范围与提示

对于 100\% 的数据,保证 2 \leq n \leq 10 或者 n = 16 ,且 m 的位数在 100 位以内