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

An đang học về tính chia hết. Cô giáo viết lên bảng hai số nguyên dương \(L\) và \(R\) rồi hỏi An: "Trong đoạn từ \(L\) đến \(R\), có bao nhiêu số chia hết cho \(3\)?"

An chưa biết cách làm nhanh, em hãy giúp An viết chương trình đếm số lượng số chia hết cho \(3\) trong đoạn \([L, R]\) 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 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ố trong đoạn \([L, R]\) chia hết cho \(3\).

Ví dụ

Ví dụ 1

Input:
1 10
Output:
3

Ví dụ 2

Input:
3 15
Output:
5

Subtask