C. Function
time limit per test
10 s
memory limit per test
64 megabytes
input
standard input
output
standard output

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))& {m \gt 1}\\ f(n)& {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.

Example
Input
2
3 4
4102 642
Output
12
21262