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~.

Input:

• Dòng đầu chứa số nguyên dương ~T~ là số lượng testcase (~1 ≤ T ≤ 10^5~);
• Mỗi test được mô tả trên hai dòng là ~L~ và ~R~ (~1 ≤ L ≤ R ≤ 10^{10000}~).

Output:

• 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~

Subtasks:

• Có ~50 \%~ số test với ~R ≤ 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.

Sample Input:

2
1 100
101 200

Sample Output:

4
2

Giải thích:

• Các số thỏa mãn testcase 1 là: ~19, 38, 76, 95~.