Chia Hết Cho Mọi Chữ Số

Một số nguyên dương được gọi là hợp lệ nếu nó chia hết cho từng chữ số khác $0$ xuất hiện trong biểu diễn thập phân của chính nó. Chữ số $0$ không đặt ra điều kiện chia hết.

Với mỗi đoạn đóng $[l,r]$, hãy đếm các số hợp lệ trong đoạn.

Input

• Dòng đầu chứa số nguyên $T$.
• Mỗi trong $T$ dòng tiếp theo chứa hai số nguyên $l$ và $r$.

Output

• Với mỗi truy vấn, in số lượng số hợp lệ trong $[l,r]$.

Constraints

• $1\le T\le 10$.
• $1\le l\le r\le 9\cdot 10^{18}$.
• Chữ số $0$ không tạo điều kiện chia hết.

Scoring

• Subtask $1$ ($50$ điểm): $T\le 5$ và $r\le 200,000$.
• Subtask $2$ ($50$ điểm): Không có giới hạn bổ sung.

Example

1
10 20

5