Tý có một hôm, cô giáo viết lên bảng hai số nguyên dương \(L\) và \(R\) rồi đố cả lớp: "Có bao nhiêu số trong đoạn từ \(L\) đến \(R\) mà tổng các chữ số ở vị trí chẵn bằng tổng các chữ số ở vị trí lẻ?".

Các vị trí được đánh số từ trái sang phải, bắt đầu từ \(1\). Ví dụ, số \(12345\) có vị trí lẻ là \(1, 3, 5\) với tổng \(1+3+5=9\), vị trí chẵn là \(2, 4\) với tổng \(2+4=6\).

Em hãy giúp các bạn trong lớp giải bài toán này nhé!

Yêu cầu: Đếm số lượng số trong đoạn \([L, R]\) thỏa mãn điều kiện trên.

Đị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

Đầu vào

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

Đầu ra

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

Ví dụ

Đầu vào:

1 50

Đầu ra:

4

Giải thích

Các số thỏa mãn trong \([1, 50]\): \(11, 22, 33, 44\) (tổng vị trí lẻ bằng tổng vị trí chẵn).

Subtask