Problem Description

Maddy came to a faded tall tower. On the stone tablet under the tower, there was a number $n$ carved on it.
Maddy found a mechanism on a stone nearby. She pressed it and found that the number on the tablet changed as follows:

• Split the decimal representation of $n$ into digits, square each digit, and then concatenate them in the original order to form a new number $n'$.

Maddy was curious. She pressed the mechanism $m$ times. She recorded the original $n$ and the results after pressing it these $m$ times, for a total of $m+1$ numbers: $n, n', n'', \dots, n^{(m)}$.
Maddy wants to know the value $ans$ of the sum of these $m+1$ numbers modulo $9$. Please help her compute it.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^3$), the number of test cases.
For each test case, the only line contains two integers $n$ and $m$ ($1 \le n, m \le 10^9$), representing the number carved on the tablet and the number of times Maddy pressed the mechanism.

Output Format

For each test case, output one integer $ans$ on a single line, representing the sum of the above results modulo $9$.

4
1 100
2 4
74700 1
2279 1

2
6
6
5

Hint

Sample 1 Explanation

For the 1st sample case, after pressing the mechanism, $1$ always stays $1$. Each result is $1$, so the total sum is $1 \times 101 = 101$, and the modulo is $101 \bmod 9 = 2$.
For the 2nd sample case, the number changes as follows: $2 \to 4$, $4 \to 16$, $16 \to 136$, $136 \to 1936$. The sum of these 5 numbers modulo $9$ is $(2 + 4 + 16 + 136 + 1936) \bmod 9 = 2094 \bmod 9 = 6$.
For the 3rd sample case, the number changes as follows: $74700 \to 49164900$.
For the 4th sample case, the number changes as follows: $2279 \to 444981$.

Hint

Taking modulo $9$ means the remainder after dividing the number by $9$.

Translated by ChatGPT 5