PIPI最近学完了动态规划课程，上完课后他觉得DP不过如此，于是马上找了一道题进行挑战。
经过PIPI的思考，这道题目PIPI推理出了状态转移方程：DP[i]=DP[i-1]+minDigit(DP[i-1])*maxDigit(DP[i-1])。其中minDigit(x)与maxDigit(x)表示x的十进制上每一位的最小值和最大值。比如minDigit(213)=1，maxDigit(213)=3。
题目给出了DP[1]和n的值，要求PIPI给出DP[n]的值。可是n的大小达到了10^18，难道此题得通过矩阵快速幂加速吗，可是PIPI并不会这个算法。
PIPI十分苦恼，于是他只得寻求你的帮助。 

第一行一个正整数T表示数据组数，T<=1000。
接下来T行，每行两个正整数DP[1]与n，其中DP[1]<=10^18,n<=10^18。

对于每组数据输出DP[n]的值。

样例解释： 
DP[1]=487。
DP[2]=487+4*8=519。
DP[3]=519+1*9=528。
DP[4]=528+2*8=544。
DP[5]=544+4*5=564。