Problem1469--PIPI学DP

1469: PIPI学DP

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 132  Solved: 59
[Submit] [Status] [Web Board] [Creator:]

Description

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十分苦恼,于是他只得寻求你的帮助。 

Input

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

Output

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

Sample Input

1
487 5

Sample Output

564

HINT

样例解释: 
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。

Source/Category