Background

Your brain is over

I've invaded your brain

Destruction your brain

Destroy your brain cells

WE ARE THE BRAIN HACKER

Description

$f(x)$ 计算的是 $x$ 中每个数字所产生的封闭区域的总数。例如 $f(114514)=0+0+1+0+0+1=2$，$f(1919810)=0+1+0+1+2+0+1=5$。

定义递归函数 $g(x)$：

$$\begin{cases} g^0(x)=x \\ g^k(x)=f(g^{k-1}(x)) \; if \; k \geq 1 \end{cases}$$

例如 $g^2(1145141919810)=f(f(1145141919810))=f(7)=0$。

Format

Input

有多个测试用例。输入的第一行包含一个整数 $T$（$T \leq 10^4$)，表示测试用例的数量。 之后的每行包含两个整数 $x$ 和 $k$（$0 \leq x,k \leq 10^{10000}$）。正整数不带前导零，零则正好是一个 "0"。

Output

对每个测试用例输出一行，其中包含一个整数，表示 $g^k(x)$ 的值。

Samples

5
1234567890 1
1145141919810 0
99999999999 0
0000000000000 2
1145144444444444444 2

6
1145141919810
99999999999
0
0