Bình đang tập đếm theo một cách rất đặc biệt: bạn ấy chỉ quan tâm đến những số có tổng các chữ số bằng đúng một giá trị \(K\) nào đó.

Hôm nay, cô giáo cho Bình hai số \(L, R\) và một số \(K\), yêu cầu đếm xem trong đoạn \([L, R]\) có bao nhiêu số mà tổng các chữ số của nó bằng \(K\).

Em hãy giúp Bình giải bài toán này nhé!

Đị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 162\)).

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 5
Output:
2

Giải thích: Hai số thỏa mãn là \(5\) và \(14\) (vì \(1 + 4 = 5\)).

Ví dụ 2

Input:
10 100 10
Output:
9

Subtask