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\)

Scoring

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

Example

2
1 100
101 200

4
2