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

Dũng là một cậu bé rất cầu toàn. Cậu ấy thích những số mà hai chữ số đứng cạnh nhau không được giống nhau. Ví dụ, số \(121\) thì được, nhưng số \(112\) thì không được vì có hai chữ số 1 đứng cạnh nhau.

Cho hai số \(L\) và \(R\), hãy đếm xem trong đoạn \([L, R]\) có bao nhiêu số 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

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 15
Output:
14

Giải thích: Chỉ có số \(11\) bị loại.

Ví dụ 2

Input:
90 113
Output:
20

Subtask