Tý cần giải bài toán sau:

Minh là một học sinh rất yêu thích toán học. Cậu ấy phát hiện ra một tính chất thú vị: có những số mà nó chia hết cho từng chữ số của nó. Ví dụ, số \(12\) chia hết cho \(1\) và chia hết cho \(2\).

Hãy giúp Minh đếm xem trong đoạn \([L, R]\) có bao nhiêu số có tính chất này.

Lưu ý: Các chữ số của số không được chứa chữ số \(0\) (vì không thể chia cho \(0\)).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Input

• Một dòng duy nhất chứa hai số nguyên \(L, R\) (\(0 \le L \le R \le 10^{18}\)).

Output

• Một số nguyên duy nhất là số lượng số thỏa mãn.

Ví dụ

Ví dụ 1

Input:
1 20
Output:
13

Giải thích: Các số thỏa mãn là \(1,2,3,4,5,6,7,8,9,11,12,15\) (và \(10\) không thỏa vì có chữ số 0).

Ví dụ 2

Input:
100 150
Output:
17

Subtask