CxForce对数字有他自己的偏好,在他看来,一个数是美的,当且仅当这个数字从前往后读和从后往前读是一样的。

例如:232是一个美的数字;而233则不是,因为它从前往后读为233,从后往前读为332,两者不相等;对于不美的数字, CxForce 决定使用魔法将它们变成美的数字;对一个数施加魔法,可以看作将这个数字加上它从后往前读的数字,例如233被施加魔法之后,233+332=565,经过一次魔法,这个数字就变美了;

请注意, CxForce 喜欢(会且仅会)在十进制下施法;由于 CxForce 学习数数的时候在开小差,所以他想请你告诉他一个任意进制的数字经过几次魔法之后可以变成十进制下美的数字，然后他就会开始施法。当然，如果需要施法的次数大于等于10次，CxForce会觉得很烦，他就不会想施法了！

输入

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

输出

记需要施法的次数为answer，若answer小于10则输出answer，否则输出"It is a waste of magic."（不含引号，半角字符）。

57 16

4

提示

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