Even-dominant Numbers

Time limit3sMemory limit2048 MB

Summary

For each query, count the integers x in [l, r] whose even digit count, together with the digits of floor(sqrt(x)), exceeds the odd digit count.

Level: Hard8 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

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]$ .

Input

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.

Output

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

Examples1

Example 1
Input
```
1
1 10
```
Expected output
```
3
```