Iterated Function Summation

Problem Description

Define the function $f(x)$:

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

where $k$ is the number of digits of $x$. For example, $f(2013)=(2013\times 13\times 13\times 3)\bmod 2014$.

Define the function $g(x,m)$:

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

For example, $g(x,2)=f(f(x))$.

You are given $T$ groups of $x, m$. For each group, compute the value of $\displaystyle\sum_{i=1}^{m} g(x,i)$.

Input Format

The first line contains an integer $T$ ($1\le T\le 20$), the number of test cases.

The next $T$ lines each contain two integers $x, m$ ($1\le x,m\le 10^9$).

Output Format

For each test case, output one integer on a single line.

Sample Input

2
3 4
4102 642

Sample Output

12
21262