NUM19

Cho hai số nguyên dương $L,R$. Hãy đếm xem có bao nhiêu số nguyên dương $x$ thuộc đoạn $[L,R]$ chia hết cho $19$; sao cho ở dạng biểu diễn thập phân, $x$ không chứa hai chữ số nào có tổng chia hết cho $3$.

Hai chữ số ở đây là hai chữ số ở hai vị trí khác nhau bất kỳ của $x$ (không nhất thiết kề nhau). Ví dụ $323=19·17$ không thỏa mãn vì chữ số đầu và chữ số cuối có tổng $3+3=6$ chia hết cho $3$.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $T$ là số lượng testcase ($1\le T\le {10}^5$);
• Mỗi testcase gồm hai số nguyên dương $L$ và $R$ ($1\le L\le R\le {10}^{10000}$), cách nhau bởi dấu cách hoặc dấu xuống dòng. Các số không có chữ số $0$ ở đầu.

Dữ liệu ra

Với mỗi testcase, ghi trên một dòng số lượng số nguyên dương $x$ tìm được, sau khi chia lấy dư cho $1000000007$.

Ràng buộc

• $1\le T\le {10}^5$
• $1\le L\le R\le {10}^{10000}$
• Tổng độ dài (số chữ số) của tất cả các số $R$ trong $T$ testcase không vượt quá ${10}^6$.

Subtasks

• Có $50\%$ số test với $R\le {10}^6$;
• Có $30\%$ số test với tổng độ dài của tất cả các số $R$ trong $T$ testcase không vượt quá ${10}^3$;
• Có $20\%$ số test với ràng buộc gốc.

Ví dụ