# 2021牛客暑期多校训练营1 F题 Find 3-friendly Integers

A positive integer is 3-friendly if and only if we can find a continuous substring in its decimal representation, and the decimal integer represented by the substring is a multiple of $3$.

For instance:

1. ${104}$ is 3-friendly because "0" is a substring of "104" and 0mod   $0\mod3=0$.
2. ${124}$ is 3-friendly because "12" is a substring of "124" and $12\mod3=0$ . "24" is also a valid substring.
3. ${17}$ is not 3-friendly because $1\mod 3≠0, 7\mod 3≠0, 17\mod 3≠0$ .

Note that the substring with leading zeros is also considered legal.

Given two integers ${L}$ and ${R}$ , you are asked to tell the number of positive integers ${x}$ such that $L≤x≤R$ and ${x}$ is 3-friendly.

## 输入描述:

There are multiple test cases. The first line of the input contains an integer $T(1 \le T \le 10000)$ , indicating the number of test cases. For each test case:

The only line contains two integers $L,R(1 \le L \le R \le 10^{18})$, indicating the query.

## 输出描述:

For each test case output one line containing an integer, indicating the number of valid ${x}$ .

## 示例1

### 输入

3
4 10
1 20
1 100

### 输出

3
11
76

## 题解

1. 当数字大于100时，所有数一定满足条件（任意三个10以内数字，一定满足数字之间有某种相加方式得到的结果是3的倍数）
2. 100以内，打表或者暴力判断均可。

## 代码

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn = 2e3 + 10;
typedef long long ll;

int T;
ll l, r;
int a[100] = {
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1,
0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};

int main() {
cin >> T;
while (T--) {
cin >> l >> r;
ll sum = 0;
if (l >= 100) {
sum = r - l + 1;
} else {
if (r < 100) {
for (int i = l; i <= r; i++) {
if (a[i]) sum++;
}
} else {
sum += r - 100 + 1;
for (int i = l; i <= 99; i++) {
if (a[i]) sum++;
}
}
}
cout << sum << endl;
}
return 0;
}