Một số được gọi là số thú vị nếu số đó là số chẵn và có tổng các chữ số chia hết cho 3. Ví dụ số 18 là một số thú vị vì 18 là số chẵn và tổng các chữ số là ~1+8=9~ là số chia hết cho 3, trong khi đó số 20 thì không là số thú vị vì tổng các chữ số của 20 không chia hết 3.

Yêu cầu: Hãy đếm số lượng số thú vị trong đoạn ~[a; b]~.

Input

Dòng đầu tiên ghi số nguyên dương ~T~ là số lượng testcase ~(T \le 10^5)~; ~T~ dòng kế tiếp, mỗi dòng ghi hai số nguyên dương ~a~, ~b~ ~(a \le b \le 10^{18})~.

Output

Gồm ~T~ dòng, mỗi dòng tương ứng là số lượng số thú vị trong đoạn ~[a; b]~.

Sample Input 1

3
1 10
5 20
10 50

Sample Output 1

1
3
7

Giải thích

• Từ ~1 \rightarrow 10~ ta có các số thú vị là 6.
• Từ ~5 \rightarrow 20~ có các số thú vị là: 6, 12, 18.
• Từ ~10 \rightarrow 50~ có các số thú vị là: 12, 18, 24, 30, 36, 42, 48.

Subtasks