Equanimous

Alice, Bob, and Eve play a game on craft paper. Each time Eve names a natural number, Alice and Bob write that number in decimal on their own paper, put a plus or minus sign before each digit, and evaluate the expression they wrote. The player with the smaller absolute value wins. If the absolute values are equal, the game is a draw and they play one more round.

If they are smart, the game never ends. So they turn to the optimal solution of the puzzle. Let $f(m)$ be the minimal absolute value that can be built from $m$. Find $f(m)$ for $l \leq m \leq r$.

They also set a puzzle for you. For several queries $(l, r)$, find the sum of all integers $m$ with $l \leq m \leq r$ and $f(m) = k$, for each $k = 0, 1, \ldots, 9$. Report the answers modulo $10^9 + 7$.

The first line contains one integer $n$ ($1 \leq n \leq 5000$), the number of queries. Each of the next $n$ lines contains two integers $l$ and $r$ ($1 \leq l \leq r \leq 10^{100}$).

For each query, print one line with ten space-separated integers. The $k$-th integer, counting from $k = 0$ to $k = 9$, is the sum of all $m$ with $l \leq m \leq r$ and $f(m) = k$, modulo $10^9 + 7$.

The digits of $19260817$ are $\{1, 9, 2, 6, 0, 8, 1, 7\}$, which can build the expression $(+1-9-2-6+0+8+1+7)$. Its value and absolute value are both $0$.

The digits of $19260818$ are $\{1, 9, 2, 6, 0, 8, 1, 8\}$, which can build the expression $(+1-9+2+6-0-8-1+8)$. Its value is $-1$ and its absolute value is $1$.