P16213 [ECUSTPC 2025] Tower No. 16

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.

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.

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

### 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