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.

제한

힌트