Sau khi rời khỏi khu vực Hang Sơn Đoòng, ledinhbaonam, PhuocThien, uia và Prototype tiếp tục hành trình đến một địa điểm đặc biệt nằm sâu trong lòng Hà Nội — nơi được biết đến với tên gọi Viện Nghiên cứu cao cấp về Toán.
Trong phòng nghiên cứu trung tâm, uia phát hiện một dãy số đặc biệt được ghi lại trên một bảng đá:

\(0, 1, 5, 4, 0, 5, 1, 0, 4, 5, 5, 6, 0, 9, \dots\)

Dãy được mở rộng vô hạn theo một quy luật chưa được giải thích đầy đủ, nhưng đảm bảo luôn xác định được giá trị tại mọi vị trí.
Sau một hồi lâu suy nghĩ, cả 4 bạn vẫn chưa thể tìm ra quy luật của bài này, các bạn coder thông minh hãy giúp các bạn giải được bài toán này nhé!

Nhiệm vụ

Bạn được cho \(Q\) truy vấn.

Mỗi truy vấn gồm hai số nguyên \(l, r\).

Hãy tính tổng các phần tử của dãy từ vị trí \(l\) đến \(r\).

Input

• Dòng đầu chứa số nguyên \(Q\) (\(1 \le Q \le 2 \times 10^5\))
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le 10^{18}\))

Output

• Với mỗi truy vấn, in ra tổng các phần tử trong đoạn \([l, r]\)

Example

3
1 3
4 9
1 11

6
14
30

1
999999999999000000 1000000000000000000

3100000