#P1148. Find 3-friendly Integers
Find 3-friendly Integers
Background
2021nowcoder多校day1 数据手造,如果想品尝原汁原味的数据,请在nowcoder购买
Description
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 33.
For instance:
- 104 is 3-friendly because "0" is a substring of "104" and.
- 124 is 3-friendly because "12" is a substring of "124" and . "24" is also a valid substring.
- 17 is not 3-friendly because $1 \mod 3 \ne 0, ~7 \mod 3 \ne 0, ~17 \mod 3 \ne 01mod3$
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 and x is 3-friendly.
Format
Input
There are multiple test cases. The first line of the input contains an integer, indicating the number of test cases. For each test case:
The only line contains two integers , indicating the query.
Output
For each test case output one line containing an integer, indicating the number of valid x.
Samples
3
4 10
1 20
1 100
3
11
76
Limitation
1s, 1024KiB for each test case.