题目背景

{- The Monad class defines the basic operations over a monad, 
	a concept from a branch of mathematics known as "category theory".
	From the perspective of a Haskell programmer, however, 
	it is best to think of a monad as an abstract datatype of actions.
	The do expressions provide a convenient syntax for writing monadic expressions.-}
class Applicative m => Monad m where
	-- Inject a value into the monadic type. 
	return :: a -> m a
	return = pure
	-- Sequentially compose two actions,
	-- passing any value produced by the first as an argument to the second.
	(>>=) :: m a -> (a -> m b) -> m b
	-- Sequentially compose two actions, discarding any value produced by the first,
	-- like sequencing operators (such as the semicolon) in imperative languages.
	(>>) :: m a -> m b -> m b
	m >> k = m >>= \_ -> k

我为什么要选计算概论实验班？

题目描述

对于一个不含前导 0 的正整数 $a$，如果能将 $a$ 的数位按照某种顺序排列以后，恰好变成 $2\cdot a$，那 $a$ 就是魔数。例如，$27489105$ 是魔数，而 $154147$ 不是。

现在问你很多个问题，每个问题会给你一个区间 $[l,r]$，你要回答 $[l,r]$ 内有多少个魔数。

输入格式

第一行一个整数 $T$ 表示询问组数。

接下来 $T$ 行，每行两个正整数 $l,r$ 表示询问区间。

输出格式

共 $T$ 行，每行一个非负整数表示答案。

样例一

input

10
1 10
1 100
1 1000
1 10000
1 100000
1 1000000
1 10000000
1 100000000
1 1000000000
1 10000000000

output

0
0
0
0
0
12
300
4332
52236
450972

限制与约定

对于前 $20\%$ 的数据，$r\le 10^6$。

对于前 $40\%$ 的数据，$r\le 10^8$。

对于前 $60\%$ 的数据，$r\le 10^9$。

对于前 $80\%$ 的数据，$r\le 10^{10}$，$T\le 5$。

对于 $100\%$ 的数据，$1\le l\le r\le 10^{12}$，$1\le T\le 10^5$。