题目描述

Maddy 来到了一座褪色的高塔面前，高塔下方的石碑上刻着一个数字 $n$。
Maddy 发现旁边的石头上有一个机关，她按下了机关，发现石碑上的数字如下变化：

• 将这个数字 $n$ 的十进制表达中的每一位都拆开后取一个平方，再按原先顺序连成一个新的数字 $n'$。

Maddy 很好奇，她按了 $m$ 次机关，她记录下了原本的 $n$ 以及这 $m$ 次按下机关之后的得数，共 $m+1$ 个数字 $n, n', n'', \dots, n^{(m)}$。
Maddy 希望知道上述 $m+1$ 个得数之和对 $9$ 取模的值 $ans$ 是多少，请帮助她求出。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10^3$)，表示数据组数。
每组测试数据输入的唯一一行输入两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^9$) 分别表示石碑上所刻的数字和 Maddy 所按机关的次数。

输出格式

每组测试数据输出一行一个整数 $ans$，表示上述得数之和对 $9$ 取模的答案。

4
1 100
2 4
74700 1
2279 1

2
6
6
5

提示

样例 1 解释

对于第 1 组样例，$1$ 在按下机关后总还是 $1$，每次的得数都为 $1$，总和为 $1 \times 101 = 101$，取模为 $101 \bmod 9 = 2$。
对于第 2 组样例，数字变化如下：$2 \to 4$，$4 \to 16$，$16 \to 136$，$136 \to 1936$，这 5 个数字的和对 9 取模为 $(2 + 4 + 16 + 136 + 1936) \bmod 9 = 2094 \bmod 9 = 6$。
对于第 3 组样例，数字变化如下：$74700 \to 49164900$。
对于第 4 组样例，数字变化如下：$2279 \to 444981$。

提示

一个是 对 9 取模表示的是这个数除以 9 之后产生的余数。