Cho hai số nguyên dương L, R. Đếm các số nguyên dương x thuộc đoạn [L, R], chia hết cho 19 và không chứa hai chữ số nào có tổng chia hết cho 3. Điều kiện này xét mọi cặp vị trí khác nhau, kể cả khi hai vị trí không kề nhau. Biểu diễn thập phân không có chữ số 0 ở đầu.

Dữ liệu vào

Dòng đầu chứa T (1 ≤ T ≤ 10⁵).

Mỗi trường hợp gồm hai dòng lần lượt chứa L và R (1 ≤ L ≤ R ≤ 10¹⁰⁰⁰⁰), viết trong hệ thập phân, không có số 0 ở đầu.

Tổng độ dài các số R trong một tệp dữ liệu không vượt quá 10⁵.

Kết quả

Với mỗi trường hợp, in một dòng chứa số lượng tìm được, lấy dư cho 10⁹ + 7.

Ví dụ

Input

2
1
100
101
200

Output

4
2

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.