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

Cường là một cậu bé rất mê tín. Cậu ấy cho rằng số 13 mang lại điềm gở, nên cậu ấy chỉ thích những con số không chứa hai chữ số 1 và 3 đứng cạnh nhau theo đúng thứ tự (tức là không có xâu con "13").

Cho hai số \(L\) và \(R\), hãy đếm xem có bao nhiêu số trong đoạn \([L, R]\) không chứa xâu "13".

Đị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ố \(13\) chứa "13", các số còn lại đều thỏa mãn.

Ví dụ 2

Input:
130 140
Output:
10

Giải thích: Các số \(130, 131, 132, 133, 134, 135, 136, 137, 138, 139\) đều chứa "13" ở đầu.

Subtask