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.   is 3-friendly because "0" is a substring of "104" and .
2.   is 3-friendly because "12" is a substring of "124" and . "24" is also a valid substring.
3.   is not 3-friendly because .

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

Given two integers  and , you are asked to tell the number of positive integers  such that  and  is 3-friendly.

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.

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

3
4 10
1 20
1 100

3
11
76