꿈속의 표

아니차는 이상한 꿈을 꾸고 있다. 꿈속에는 끝없이 넓은 칠판이 있고, 그 위에 행과 열이 무한히 이어지는 표가 그려져 있다. 표에 적힌 수는 무한히 많지만, 같은 수가 나타나는 횟수는 언제나 유한하다.

표의 규칙은 단순하다. 각 행의 첫 칸에는 그 행의 번호가 적혀 있다. 첫 열이 아닌 칸에는 바로 왼쪽 칸의 수와 그 수를 십진법에서 거꾸로 뒤집은 수를 더한 값이 적혀 있다.

$i$행 $j$열의 값을 $T(i, j)$라고 하면 다음이 성립한다.

$T(i, 1) = i$

$T(i, j) = T(i, j - 1) + \mathrm{rev}(T(i, j - 1)) \quad (j > 1)$

표의 앞쪽 몇 행과 몇 열이다. 표는 아래쪽과 오른쪽으로 끝없이 이어진다.

아니차는 칠판을 무심코 지나쳤지만, 칠판 뒤에 놓인 램프가 눈에 들어왔다. 램프도 아니차를 알아보고, 안에서 친절한 유령 보조가 나왔다.

"아니차! 내가 내는 질문 $Q$개에 모두 맞게 답하면 웨하스 한 봉지와 쿠키 한 봉지 중에서 원하는 쪽을 주겠다. 질문마다 정수 $A$와 $B$를 주겠으니, 구간 $[A, B]$에 속하는 수가 칠판 위에 모두 몇 번 나타나는지 답해라."

같은 값이 여러 칸에 적혀 있으면 칸의 개수만큼 세어야 한다. 아니차는 끝내 답을 하지 못하고 잠에서 깼다.

첫째 줄에 질문의 개수 $Q$가 주어진다. ($1 \le Q \le 10^5$)

다음 $Q$개 줄에 질문이 한 개씩 주어진다. 각 줄에는 정수 $A$와 $B$가 공백을 사이에 두고 주어진다. ($1 \le A \le B \le 10^{10}$)

$Q$개 줄을 출력한다. $i$번째 줄에는 $i$번째 질문의 답, 곧 값이 $A$ 이상 $B$ 이하인 칸의 개수를 출력한다.

$\mathrm{rev}(x)$는 $x$를 십진법에서 거꾸로 뒤집어 읽은 수이고, 앞에 남는 $0$은 버린다. 예를 들어 $\mathrm{rev}(213) = 312$이고, $\mathrm{rev}(406800) = 008604 = 8604$이다.