#P1148. Find 3-friendly Integers

    ID: 200 Type: Default 1000ms 256MiB Tried: 3 Accepted: 1 Difficulty: 10 Uploaded By: Tags>其他暴力多校训练牛客多校数位DP

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" and0mod3=00mod3=0 0 \mod 3 = 00mod3=0.
  • 124 is 3-friendly because "12" is a substring of "124" and 12mod3=012mod3=012 \mod 3 = 012mod3=0. "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 thatLxR L≤x≤R and x is 3-friendly.

Format

Input

There are multiple test cases. The first line of the input contains an integerT(1T10000) T(1≤T≤10000), indicating the number of test cases. For each test case:

The only line contains two integers L,R(1LR1018)L,R(1≤L≤R≤10^{18}), 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.