Số ~n~ được gọi là đẹp nếu thoả mãn đồng thời các điều kiện:

• Có thể biểu diễn ~n~ thành tổng của 2 số dương có cùng tổng các chữ số.
• Có thể biểu diễn ~n~ thành tổng của 3 số dương có cùng tổng các chữ số.

Nhiệm vụ của bạn là trả lời ~q~ truy vấn, trong đó ~1 \le q \le 10^5.~ Mỗi truy vấn gồm hai số L, R với ~1 \le L \le R \le 10^{18}~ và đếm xem trong đoạn ~[L;R]~, có tất cả bao nhiêu số đẹp?

Sample input

2
1 10
2024 2026

Sample output

1
1

Giải thích

Ký hiệu ~S(n)~ là tổng chữ số của số nguyên dương ~n~. Ở ví dụ 1, ta có số đẹp duy nhất là ~6 \in [1;10]~ vì có thể viết ~6=3+3=2+2+2~; ở ví dụ 2, ta có số đẹp duy nhất là ~2025~ vì ~2025 = 2016+9 = 2013+6+6~ vì ~S(2016)=S(9)=9~ và ~S(2013)=S(6)=S(6)=6~, kiểm tra trực tiếp được các số khác thì không thoả mãn.