函数迭代求和

题目描述

定义函数 $f(x)$：

$$f(x)=\prod_{i=1}^{k}\bigl(x\bmod 10^i\bigr)\bmod (x+1),$$

其中 $k$ 为 $x$ 的位数。例如 $f(2013)=(2013\times 13\times 13\times 3)\bmod 2014$。

再定义函数 $g(x,m)$：

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

例如 $g(x,2)=f(f(x))$。

给定 $T$ 组 $x,m$，对每组求 $\displaystyle\sum_{i=1}^{m} g(x,i)$ 的值。

输入格式

第一行一个整数 $T$（$1\le T\le 20$），表示数据组数。

接下来 $T$ 行，每行两个整数 $x,m$（$1\le x,m\le 10^9$）。

输出格式

对每组数据输出一行一个整数。

样例输入

2
3 4
4102 642

样例输出

12
21262