짝수 우세 수

이 문제는 인터랙티브 문제이다.

$x$의 십진 표기에 있는 짝수 자릿수의 총합과 $\left\lfloor \sqrt{x} \right\rfloor$(즉 $x$의 제곱근을 내림한 정수)의 십진 표기에 있는 짝수 자릿수의 총합을 더한 값이 같은 두 수의 홀수 자릿수 총합보다 크면, $x$를 짝수 우세 수라고 한다.

예를 들어, $222\,213$은 짝수 우세 수이다. $222\,213$과 $\left\lfloor \sqrt{222\,213} \right\rfloor = 471$의 짝수 자릿수는 모두 $5$개로, 홀수 자릿수 $4$개보다 많기 때문이다. 반면 $2$는 짝수 우세 수가 아니다. $2$와 $\left\lfloor \sqrt{2} \right\rfloor = 1$의 짝수 자릿수와 홀수 자릿수가 각각 $1$개로 같기 때문이다.

구간 $[\ell, r]$에 속한 짝수 우세 수의 개수를 구하라.

첫 줄에 정수 $t$ ($1 \leq t \leq 10\,000$)가 주어진다. 질의의 개수이다.

다음 $t$개의 줄에는 각각 정수 $\ell_i$와 $r_i$ ($1 \leq \ell_i \leq r_i \leq 10^{12}$)가 주어진다. $i$번째 질의의 구간을 나타낸다.

각 질의마다 주어진 구간에 속한 짝수 우세 수의 개수를 한 줄에 출력한다.