如果我们定义 $f(0) = 1, f(1) = 0, f(4) = 1, f(8) = 2, f(16) = 1, \dots$，你知道函数 $f$ 的含义吗？ 实际上，$f(x)$ 计算的是 $x$ 中每个数字所产生的封闭区域的总数。下表展示了每个数字所产生的封闭区域数量：
| 数字 | 封闭区域 | 数字 | 封闭区域 |
|---|---|---|---|
| 0 | 1 | 5 | 0 |
| 1 | 0 | 6 | 1 |
| 2 | 0 | 7 | 0 |
| 3 | 0 | 8 | 2 |
| 4 | 1 | 9 | 1 |
例如，$f(1234) = 0 + 0 + 0 + 1 = 1$，且 $f(5678) = 0 + 1 + 0 + 2 = 3$。
我们现在通过以下方程定义一个递归函数 $g$：
$$ \begin{cases} g^0(x) = x \\ g^k(x) = f(g^{k-1}(x)) \quad \text{若 } k \geq 1 \end{cases} $$
例如，$g^2(1234) = f(f(1234)) = f(1) = 0$，且 $g^2(5678) = f(f(5678)) = f(3) = 0$。
给定两个整数 $x$ 和 $k$，请计算 $g^k(x)$ 的值。
输入格式
包含多组测试数据。第一行包含一个整数 $T$（约 $10^5$），表示测试数据的组数。对于每组测试数据： 第一行包含两个整数 $x$ 和 $k$ ($0 \leq x, k \leq 10^9$)。正整数不含前导零，零由单个字符 '0' 表示。
输出格式
对于每组测试数据，输出一行，包含一个整数，表示 $g^k(x)$ 的值。
样例
输入 1
6 123456789 1 888888888 1 888888888 2 888888888 999999999 98640 12345 1000000000 0
输出 1
5 18 2 0 0 1000000000