Tại Đại Học Công Nghệ nổi tiếng \(Combinatoria\) có giáo sư p2o2HuaGiaBao đang giảng lý thuyết quan trọng về tổ hợp như sau:

• \(C^{n}_k = \frac{n!}{k!\times (n-k)!}\), công thức này áp dụng để tính số lượng hoán vị để chọn \(k\) vật từ \(n\) vật phân biệt. (Chú ý: Mỗi hoán vị chỉ thay đổi thứ tự được coi là giống nhau)
• \(P^{n}_k = \frac{n!}{(n-k)!}\), công thức này áp dụng để tính số lượng hoán vị để chọn \(k\) vật từ \(n\) vật phân biệt. (Chú ý: Mỗi hoán vị chỉ thay đổi thứ tự được coi là khác nhau)

Giáo sư này giao một bài tập cho học sinh rằng:

Đếm bộ \(3\) số khác nhau trong các số liên tiếp từ \(l\) đến \(r\) sao cho tổng của \(3\) số đó chia hết cho \(3\) trong \(Q\) truy vấn.
Vì kết quả có thể rất lớn nên mỗi kết quả phải chia lấy dư cho \(10^9 + 7\).

Vì bài tập tập này quá khó nên cần các bạn giúp đỡ ngay.

Input

• Dòng \(1\) là một số nguyên dương \(Q\) (\(1\le Q\le 10^{6}\))
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(l\) và \(r\) (\(1\le l\le r \le 10^{18}\)) cách nhau bởi một khoảng cách.

Output

• Gồm \(Q\) dòng, mỗi dòng là kết quả cho mỗi truy vấn tương ứng.

Example

1
1 10

42

Scoring

• Subtask 1 (\(25\)% points): \(1 \le l\le r \le 10^2\) và \(1\le Q\le 1\)
• Subtask 2 (\(25\)% points): \(1 \le l\le r \le 10\) và \(1\le Q\le 10^5\)
• Subtask 3 (\(25\)% points): \(1 \le l\le r \le 10^{5}\) và \(1\le Q\le 10^5\)
• Subtask 4 (\(25\)% points): Không có ràng buộc gì thêm.