L. Low Key
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob was considering all of the quantum ramifications of multiverse theory. If you consider that there are other dimensions out there with alternate versions of you, across all possible choices you could have made in your lifetime, then for every good version of you, there must be an evil version of you as well. And sometimes the good and evil multiversal counterparts can annihilate each other like antimatter if they ever come into contact with each other.

Anyway, that is all to say, Bob is having a lot of fun writing a sci-fi short story.

Alice is somewhat fatigued with all this multiverse nonsense in the current cultural mass media zeitgeist. So while Bob's doing all that, why don't you solve this fun math puzzle with her?

A positive integer $$$n$$$ is called zero-multiversal if its digits can be rearranged into two different positive integers $$$p$$$ and $$$q$$$ such that $$$|p-q|$$$ contains at least one $$$0$$$.

So, for example, $$$128$$$ is zero-multiversal, because $$$821 - 218 = 603$$$. On the other hand, it can be shown that $$$69$$$ is not zero-multiversal.

Given positive integers $$$\ell$$$ and $$$r$$$, count the number of zero-multiversal integers between $$$\ell$$$ and $$$r$$$ (inclusive).

Formally, let $$$\mathrm{digits}(m)$$$ be the multiset containing all the digits of some positive integer $$$m$$$ (by default, we assume integers are never written with leading zeros). Then, a positive integer $$$n$$$ is called zero-multiversal if there exist distinct positive integers $$$p$$$ and $$$q$$$ such that:

  • $$$p \neq q$$$
  • $$$\mathrm{digits}(p) = \mathrm{digits}(q) = \mathrm{digits}(n)$$$
  • The digit 0 appears in $$$\mathrm{digits}(|p-q|)$$$
Count the number of integers $$$n$$$ such that $$$n$$$ is zero-multiversal, and $$$\ell \leq n \leq r$$$.
Input

The first line of input contains a single integer $$$T$$$, denoting the number of test cases. The descriptions of $$$T$$$ test cases follow.

Each test case consists of a single line containing the two space-separated integers $$$\ell$$$ and $$$r$$$.

Output

For each test case, output one line containing a single integer, the answer for that test case.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 150000 \\ 0 \lt \ell \leq r \lt 10^{18} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & r \lt 10^4 \\ \hline 2 & \mathbf{30} & r \lt 10^6 \\ \hline 3 & \mathbf{20} & r \lt 10^9 \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
2
115 120
69 69
Output
6
0