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

Format

Input

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

The only line contains two integers $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.