Background

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.

Problem Description

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.

Input Format

The first line contains an integer $T$.

The next $T$ lines each contain two integers $n, k$, representing one test case.

Output Format

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

1
0 1

11

Hint

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