P9930 [NFLSPC #6] 1064 Virus

Your computer has been infected with the 1064 virus, and now all numbers stored on your computer have started to collapse. To destroy your computer more thoroughly, for an $n$-digit number in decimal, the evil 1064 virus will iterate it by some rule at least $n + 1$ times, to make sure you cannot recover it. Facing the 1064 virus, you are at a loss. But as an OIer, you want to know dao dao dao dao dao dao dao dao dao dao dao dao dao dao dao dao dao.

A digit string is defined as a string that contains only digits $0\sim 9$. Odd digits are $1, 3, 5, 7, 9$, and even digits are $0, 2, 4, 6, 8$. For a digit string $x$, let the numbers of odd digits, even digits, and total digits in it be $a, b, c$, respectively. Then $a + b = c = |x|$. Define $g(x)$ as the digit string obtained by writing $a, b, c$ in order, **without ignoring leading zeros**. For example, $g(\texttt{0}) = \texttt {011}$, $g(\texttt{1064}) = \texttt{134}$, $g(\texttt {822}) = \texttt {033}$, $g(\texttt{1092515503}) = \texttt{7310}$. Let $f_k(x)$ denote: first write the **number** $x$ into a digit string $x'$ **ignoring leading zeros**, then iterate $g(x')$ for $k$ times, and take the number represented by the resulting digit string. That is, let $x ^ * = g(g(\cdots g(x')))$ (there are $k$ applications of $g$), then $f_k(x)$ is the result of converting $x ^ *$ into a number. Given $n, k$ (**guaranteed $n < k$**), compute $\sum_{i = 0} ^ {10 ^ n - 1} f_k(i)$. There are multiple test cases.

The first line contains an integer $T$. The next $T$ lines each contain two integers $n, k$, representing one test case.

For each test case, output one integer per line, representing the answer.

For all testdata, $1\leq T\leq 60$, $0\leq n < k \leq 10 ^ 5$, $\sum k\leq 10 ^ 5$. - Subtask 1 ($30$ points): $n\leq 5$, $k\leq 15$. - Subtask 2 ($70$ points): no special constraints. Source: NFLSPC #6 F by Alex_Wei Translated by ChatGPT 5