【问题描述】

又是回文数!但这次有所不同了。

    给定一个N进制正整数,把它的各位数字上数字倒过来排列组成一个新数,然后与原数相加,如果是回文数则停止,如果不是,则重复这个操作,直到和为回文数为止。

如果N超过10,使用英文字母来表示那些大于9的数码。例如对16进制数来说,用A表示10,用B表示11,用C表示12,用D表示13,用E表示14,用F表示15。

例如:10进制87则有:

STEP1: 87+78=165

STEP2: 165+561=726

STEP3: 726+627=1353

STEP4: 1353+3531=4884

编写一个程序,输入N(2<=N<=16)进制数M(1<=M<=30000(10进制)),输出最少经过几步可以得到回文数。如果在30步以内(含30步)不可能得到回文数,则输出0。输入的数保证不为回文数。

 

【输入】

第一行一个整数L,代表输入数据的组数。

接下来L行,每行两个整数N,M

【输出】

输出L行,对于每个数据组,按题目要求输出结果,并占一行。

 

【样例输入】

2
10 87
2 110

【样例输出】

4
1