33337번 - Even-dominant Numbers 다국어인터랙티브

This is an interactive problem.

Let $x$ be an even-dominant number if the total number of even decimal digits of $x$ and $\left\lfloor \sqrt{x} \right\rfloor$ (the decimal representation of the square root of $x$, rounded down to the nearest integer) is greater than the total number of odd decimal digits of these numbers.

For example, $222\,213$ is an even-dominant number because the total number of even digits in $222\,213$ and $\left\lfloor \sqrt{222\,213} \right\rfloor = 471$ is $5$, which is greater than $4$, the total number of odd digits. However, the number $2$ is not an even-dominant number because the total number of even digits in $2$ and $\left \lfloor \sqrt{2} \right \rfloor = 1$ is equal to the total number of odd digits.

Determine the number of even-dominant numbers in the segment $[\ell, r]$.

The jury's program outputs a sequence of queries, one after the other. Once the participant's program has printed an answer for a given query, the jury's program will proceed to output the next query.

The first line contains one integer $t$ ($1 \leq t \leq 10\, 000$): the number of queries.

Each of the next $t$ lines contains two integers $\ell_i$ and $r_i$ ($1 \leq \ell_i \leq r_i \leq 10^{12}$) denoting the segment for the $i$-th query.

For each query, print a line with a single integer: the number of even-dominant numbers in the given segment.