Equanimous

Alice, Bob, Eve가 크래프트 종이로 게임을 한다. Eve가 자연수를 하나 말할 때마다 Alice와 Bob은 그 수를 십진수 표기로 자기 종이에 쓰고, 각 자릿수 앞에 + 또는 -를 붙인 뒤 만든 산술식을 계산한다. 절댓값이 작은 쪽이 이긴다. 절댓값이 같으면 무승부이고 한 판을 더 한다.

게임이 끝나지 않는다면 그들은 퍼즐의 최적해를 찾는 데 집중하게 된다. $f(m)$을 $m$으로 만들 수 있는 절댓값의 최솟값이라 하자. $l \leq m \leq r$인 $m$에 대해 $f(m)$을 구하라.

그들은 당신에게도 퍼즐을 냈다. 여러 질문 $(l, r)$이 주어지면, $l \leq m \leq r$이고 $f(m) = k$인 모든 $m$의 합을 $k = 0, 1, \ldots, 9$마다 구하라. 답은 $10^9 + 7$로 나눈 나머지로 출력한다.

첫 줄에 질문의 개수 $n$ ($1 \leq n \leq 5000$)이 주어진다. 이어지는 $n$개 줄에 각각 질문을 나타내는 정수 $l$, $r$ ($1 \leq l \leq r \leq 10^{100}$)이 주어진다.

각 질문마다 한 줄에 공백으로 구분한 정수 10개를 출력한다. $k = 0$부터 $k = 9$까지 $k$번째 정수는 $l \leq m \leq r$이고 $f(m) = k$인 모든 $m$의 합을 $10^9 + 7$로 나눈 나머지이다.

$19260817$의 자릿수는 $\{1, 9, 2, 6, 0, 8, 1, 7\}$이며, 이들로 $(+1-9-2-6+0+8+1+7)$ 식을 만들 수 있다. 이 식의 값과 절댓값은 모두 $0$이다.

$19260818$의 자릿수는 $\{1, 9, 2, 6, 0, 8, 1, 8\}$이며, 이들로 $(+1-9+2+6-0-8-1+8)$ 식을 만들 수 있다. 이 식의 값은 $-1$이고 절댓값은 $1$이다.