说明

在数字研究中，存在一种特殊的数字——回文数字。这些数字具有一种独特的性质：无论从前往后读还是从后往前读，它们的数值都是相同的。然而，并非所有的数字都是回文数字。

为了探索这一现象，一位名叫阿强的研究者设计了一个挑战：在 十进制 下将一个非回文数字转换成回文数字。他采用的方法是，将这个数字加上其反向的数字，然后重复这个过程，直到得到一个回文数字为止。

但是，阿强的耐心有限，他最多只能进行10次这样的操作。如果经过10次操作后，数字仍未变成回文数字，那么他将停止尝试，因为这将消耗他过多的时间和精力。

现在，给定一个非十进制数字及其进制，请你帮助阿强计算他需要进行多少次操作，才能使这个数字变成在 十进制 下为回文数字。如果操作次数超过10次，则请输出“Failed”以提醒阿强。

输入格式

一行两个字符串a，b，表示需要操作的数字a是一个b进制数。

输出格式

记需要操作的次数为answer，若answer小于10则输出answer，否则输出"Failed"。

样例

57 16

4

提示

对于20%测试数据，b=10
对于另外20%测试数据， b=2
对于所有测试数据，$0\leq a\leq 2^{20}$,$2\leq b\leq 16$