31801번 - 증가와 감소

대구과학고 학생인 정현이는 숫자의 규칙을 찾는 것을 좋아한다. 특히 요즘에는 증가 후 감소하는 수에 빠졌다. 증가 후 감소하는 수란, 0으로 시작하지 않도록 십진수로 표현하였을 때 각 자릿수가 증가하다가 감소하는 양의 정수를 의미한다. 다시 말해서, 양의 정수 $n=\sum _{i=0}^{k-1}a_i10^i=\overline{a_{k-1}a_{k-2}...a_1a_0}(0\leq a_i\leq 9, a_i$는 정수, $a_{k-1}\neq0)$에 대하여, 어떤 $1\leq j\leq k-2$가 존재하여 $a_{k-1}<a_{k-2}<...<a_{j+1}<a_j>a_{j-1}>...>a_1>a_0$이면 $n$을 증가 후 감소하는 수라고 한다. 예를 들어, $13586$은 $1 < 3 < 5 < 8 > 6$이므로 증가 후 감소하는 수다.

두 양의 정수 $a, b$가 주어졌을 때, $a$ 이상 $b$ 이하의 양의 정수 중 증가 후 감소하는 수가 몇 개인지 구해보자.

첫 번째 줄에 테스트케이스의 수 $t$가 주어진다.

그다음 줄부터 $t$개의 줄 동안 두 양의 정수 $a,b$가 공백으로 구분되어 주어진다.

각 테스트케이스마다 $a$ 이상 $b$ 이하인 증가 후 감소하는 수의 개수를 한 줄에 하나씩 출력한다.

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