爱数学的小明又回来辣！看了上次大家解决问题的方法后觉得自己实在是太笨了，同时引来了同是数学爱好者的小红的嘲笑，自尊心极强的小明气不过，便和小红打个赌，让小红出一道数学题给小明写，如果小明能在一周内写出来，小红就请他吃下个星期的疯狂星期四，如果做不出来就要小明请她疯狂星期四。
但是这道题实在是太难啦，小明把自己关在房间里想了一周也没能想出来，明天就是赌约的截止日期了，小明非常想吃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