问题 4342 --3友好数

4342: 3友好数★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 128  解决: 52
[提交][状态][命题人:]

题目描述

定义一个正整数是3友好数,当且仅当我们可以找到其十进制表示下的一个连续的子串,并且该子串所表示的十进制整数是 3 的倍数。

例如:
104 是 3 友好的,因为“0”是“104”的子串并且 0%3=0。
124 是 3 友好的,因为“12”是“124”的子串,12%3=0。 “24”也是一个有效的子字符串。
17 不是 3 友好的,因为 1%3 ≠ 0, 7%3 ≠ 0, 17%3≠ 0。

给定 L,R(1≤L≤R≤10^18) ,求区间 [L,R] 中有多少个3友好数。

输入

有多个测试用例。 输入的第一行包含一个整数T(1≤T≤10000),表示测试用例的数量。
对于每个测试用例:
唯一一行包含两个整数 L,R(1≤L≤R≤10^18 ),表示查询的区间。

输出

对于每组测试用例,输出一行,包含一个整数,表示答案。
样例输入
Copy
3
4 10
1 20
1 100
样例输出
Copy
3
11
76

提示

来源

[提交][状态]