단조 증가 수

Albert는 "단조 증가 수" (monotone increasing number)를 이용한 놀이를 즐겨한다. 음이 아닌 임의의 정수 $x$에 대해 $x$의 각 자리 숫자들을 좌측 (가장 큰 자릿수) 부터 우측 (가장 작은 1의 자릿수)까지 순서대로 읽었을 때 한 번도 감소하지 않으면 $x$를 단조 증가 수라 부른다. 예를 들어 0, 5, 111, 234, 2246 등은 단조 증가 수이며 121, 465 등은 단조 증가 수가 아니다.

Albert가 평소 즐겨하는 놀이는 임의의 정수 $x$가 주어졌을 때, $x$를 초과하지 않으면서 가장 큰 단조 증가 수를 찾는 놀이이다 -- 편의상 그러한 정수를 $S(x)$라 하자. 이 정의에 따르면 $x$가 단조 증가 수라면 당연히 $S(x) = x$이며 $S(5) = 5$와 $S(111) = 111$ 등이 이러한 경우에 해당한다. 반면, $x$가 단조 증가 수가 아닌 경우는 당연히 $S(x) \lt x$이며, $S(121) = 119$ 와 $S(465) = 459$ 등이 이러한 경우에 해당한다.

Albert의 놀이를 지켜보던 그의 누나는 조금 더 재미있는 놀이를 제안했다. 0 이상인 두 정수 $N \le M$이 주어졌을 때, $F(N, M) = \sum\_{x=N}^{M} S(x)$ 를 구하는 놀이이다. 즉, $N$이상 $M$이하인 모든 정수에 $x$ 대해 $S(x)$를 구하여 더한 값이 $F(N, M)$이 된다. Albert와 그의 누나를 도와 이 값을 구해보자.

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

다음 $T$줄에 걸쳐 각 줄에 $N, M$이 공백으로 구분되어 주어진다.

각 줄에 각 테스트 케이스의 정답인 $F(N, M)$을 출력한다. 단, 이 값이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

• $1 \le T \le 1000$
• $0 \le N \le M \le 10^{18}$