题解

题目描述

多多的家乡推出了一种新型彩票，规则是：如果一个数字中存在一个连续子串（去除前导零后的数值）是3的倍数，则该数字为“幸运数字”。给定范围$[L, R]$，求其中幸运数字的个数。

思路分析

这道题的核心思路是通过观察发现，任何位数≥3的数字必定包含一个子串是3的倍数，因此都是“幸运数字”。对于1位数和2位数，需要单独判断是否满足条件。预处理所有符合条件的2位数，并利用二分查找快速统计范围内的非幸运数字数目。最终，用总数减去非幸运数字的数目，即可得到幸运数字的个数。

题目内容

多乡的家乡最近推出了一种新型彩票，规则非常有趣，如果一个数字中，隐藏着一个连续的子串，且这个子中代表的数是$3$的倍数。那么这个数字就是“幸运数字"。彩票每期都会公布一个范围$[L,R]$。并从这个范围的“幸运数字”中随机选择一个作为中奖号码，

以下是一些例子，辅助理解“幸运数字”的含义:

$1.107$是“幸运数字":$0$是$107$的子串，且$0$是$3$的倍数

$2.25$不是“幸运数字":$25$有$3$个子串分别是$2、5、25$，它们都不是3的倍数

$3.2521$是"幸运数字":$21$是$2521$的子串，且$21$是$3$的倍数

注意子串必须是连续的，例:在数字$152$中，$15$是子串，$12$不是子串

以$0$开头的子串需要抹去先导$0$来考虑数值，例:在数字$103$中，$03$是一个子串，它的值为$3$，也是$3$的倍数

多多想知道$[L,R]$中有多少个幸运数字，你能帮帮他吗

输入描述

有多个测试用例。输入的第一行包含一个整数$T(1<=T<=10000)$，表示测试用例的数量;

每组输入仅一行，包含两个整数$L,R(1<=L<=R<=1e18)$

输出描述

对每个测试用例，输出一个整表示区间$[L,R]$中“幸运数字"的个数

样例1

输入

2
8 19
2 45

输出

8
31