Problem Description

Define function $f(x)= \prod \limits_{i=1}^{len} (x\%10^i)\%(x+1)$, where $len$ represents the digit length of $x$. For example, $f(1023)=(3*23*23*1023)\%1024$.

Define function $g(n,m)= \begin{cases} f(g(n,m-1))& \text{m>1}\\ f(n)& \text{m=1} \end{cases}$. For example, $g(n,2)=f(f(n))$.

You are given $n$ and $m$, please calculate $\sum\limits_{i=1}^m g(n,i)$.

Input

The input consists of multiple test cases. The first line contains an integer $T$ $(1 \leq T \leq 20)$ — the number of test cases. The description of the test cases follows.

The only line contains two integers $n,m$ $(1 \leq n,m \leq 10^9)$ .

Output

For each test case, print the answer.

2
3 4
4102 642

12
21262