Increase and Decrease

Jeonghyeon, a student at Daegu Science High School, enjoys finding patterns in numbers. Lately he has become fascinated with increase-then-decrease numbers.

A positive integer is an increase-then-decrease number if its digits increase and then decrease when written in decimal without a leading zero. Formally, for a positive integer $n=\sum_{i=0}^{k-1}a_i10^i=\overline{a_{k-1}a_{k-2}\cdots a_1a_0}$ with $0\leq a_i\leq 9$, $a_i$ an integer, and $a_{k-1}\neq 0$, $n$ is an increase-then-decrease number if there exists some $1\leq j\leq k-2$ such that $a_{k-1}<a_{k-2}<\cdots<a_{j+1}<a_j>a_{j-1}>\cdots>a_1>a_0$. For example, $13586$ is an increase-then-decrease number because $1<3<5<8>6$.

Given two positive integers $a$ and $b$, count the increase-then-decrease numbers between $a$ and $b$, inclusive.

The first line contains the number of test cases $t$.

Each of the next $t$ lines contains two positive integers $a$ and $b$, separated by a space.

For each test case, print the number of increase-then-decrease numbers between $a$ and $b$, inclusive, on its own line.

• $1 \leq t \leq 10^5$
• $1 \leq a \leq b \leq 10^6$