Tam rất thích các số nguyên dương chia hết cho 3 hoặc có tận cùng bằng

1. Vinh là bạn thân của Tam, Vinh thích tính toán và đã đưa ra ~q~ câu hỏi. Với câu hỏi thứ ~i~ là 2 số nguyên ~L_i, R_i~ ~(1 \le i \le q, 1 \le L_i \le R_i \le 10^4)~, Vinh muốn biết có bao nhiêu số mà Tam thích trong đoạn ~[L_i, R_i]~.

Yêu cầu: Hãy giúp Tam lập trình và trả lời các câu hỏi của Vinh đưa ra.

Input

• Dòng đầu tiên chứa số nguyên dương ~q~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le q)~ chứa 2 số nguyên dương ~L_i, R_i~ tương ứng câu hỏi thứ ~i~ mà Vinh đưa ra cho Tam.

Output

Ghi ra ~q~ dòng, dòng thứ ~i~ là số lượng số mà Tam thích trong đoạn ~[L_i, R_i]~.

Scoring

Sample Input 1

1
4 15

Sample Output 1

5

Sample Input 2

3
2 12
8 14
16 17

Sample Output 2

4
3
0

Notes

Các số Tam thích là 3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 33, 36, ...

• Trong ví dụ 1, có ~q = 1~ câu hỏi với đoạn ~[4, 15]~, các số thỏa mãn là 6, 9, 12, 13, 15.

• Trong ví dụ 2, có ~q = 3~ câu hỏi:

  • Đoạn ~[2, 12]~ có 4 số thỏa mãn là 3, 6, 9, 12.

  • Đoạn ~[8, 14]~ có 3 số thỏa mãn là 9, 12, 13.

  • Đoạn ~[16, 17]~ không tồn tại số nào thỏa mãn.