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

Hương có một trò chơi với những con số. Cô ấy viết một số nguyên dương lên bảng, rồi tính tích các chữ số của nó. Ví dụ, với số \(36\), tích các chữ số là \(3 \times 6 = 18\).

Hương muốn đếm xem trong đoạn \([L, R]\) có bao nhiêu số mà tích các chữ số của nó không vượt quá \(K\).

Đị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 ba số nguyên \(L, R, K\) (\(0 \le L \le R \le 10^{18}\), \(1 \le K \le 1000\)).

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 30 10
Output:
16

Giải thích: Các số thỏa mãn là \(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,20\).

Ví dụ 2

Input:
10 50 5
Output:
11

Subtask