我们定义一个整数 x 的数位集合 S(x) 为该数所有数字去重后的集合。如果集合 S(x) 中至少包含 5 个数字,且这些数字能在 0-9 的环上构成连续不间断的区间(即没有缺口),则称 x 是一个“顺子数字”。
例如:
现在给定 T 个查询,每个查询一个区间 [l, r](1 ≤ l < r < 10^18),求该区间内有多少个顺子数字。
在斗地主,若存在 5 张牌为 {a1,a2,a3,a4,a5} ,满足:
则这 5 张牌组成一个顺子。当然牌数可以更多,但是不能少于 5 张、且中间存在一个不满足连续的数字,例如 {1,2,3,5,6,7,8} 也是不构成顺子的,因为缺少了 4 。
现在,我们定义,如果一个整数 x 的 数位集合 S(x) 是一个顺子,我们则称这个整数 x 是一个"顺子数字"。例如:x=1234023 ,x 的数位集合 S(x)={1,2,3,4,0} ,由于数字连续,所以 x 是一个“顺子数字"。
对于给定的区间 [l,r] ,你需要统计其中有多少个数字是“顺子数字”。
对于整数 x ,将其每一位(个位、十位、......)上的数字都取出放入集合中,得到的集合称为数位集合。
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤10) 代表数据组数,每组测试数据描述如下:在一行上输入两个整数 l,r(1≤l<r<1018) 代表一次询问的区间。
对于每一组测试数据,新起一行。输出一个整数,表示区间中的“顺子数字”的个数。
输入
3
12341 12349
123456780 123456789
111445 114514
输出
1
10
34