爱数学的小明又回来辣！看了上次大家解决问题的方法后觉得自己实在是太笨了，同时引来了同是数学爱好者的小红的嘲笑，自尊心极强的小明气不过，便和小红打个赌，让小红出一道数学题给小明写，如果小明能在一周内写出来，小红就请他吃下个星期的疯狂星期四，如果做不出来就要小明请她疯狂星期四。

但是这道题实在是太难啦，小明把自己关在房间里想了一周也没能想出来，明天就是赌约的截止日期了，小明非常想吃KFC，于是他想到了再次向你求助，并承诺只要帮他写出这道题就把小红请的KFC分你一半。

小红设立了两个函数 $f(x)$和$g(x,m)$ ,$f(x)$的定义如下：

$$f(x)=\prod_{i=1}^{x的位数}(x \mod 10^i)\mod(x+1)$$

比如：$f(2013)=(2013 * 13 * 13 * 3)\mod 2014$

$g(x,m)$的定义如下：

$$g(x,m) \begin{cases} f(g(x,m-1)), &\ m\ >\ 1\\ f(x), &\ m\ =\ 1 \end{cases}$$

比如$g(x,2)=f(f(x))$ 现在，要你求出 $\sum_{i=1}^m g(x,i)$的值。

为了KFC，拼了！

输入格式

第一行有一个数$T$ ($1\leq T\leq 20$)，代表一共有$T$组数据。 接下来$T$行有两个数$x,m$($1\leq x,m\leq 10^9$),代表$g(x,m)$的两个参数

输出格式

对于每行测试例输出一个数字。

样例输入

2
3 4
4102 642

样例输出

12
21262