An và Khoa rất thích chơi với dãy số. Hôm nay, Khoa đố An bài toán như sau: Cho dãy A gồm n số nguyên a1, a2,..., an. Ban đầu, ai được gán bằng i (1 ≤ i ≤ n ≤ 10^18). Để bài toán thú vị hơn, Khoa biến đổi các phần tử của dãy A như sau: liên tục thay thế từng phần từ của dãy A bằng tổng các chữ số của nó cho đến khi chỉ gồm một chữ số duy nhất.

Ví dụ: với i = 197, ban đầu a197 = 197, Khoa lần lượt biến đổi giá trị của a197 như sau: 197 = 1 + 9 + 7 = 17, tiếp tục biến đổi 17 = 1 + 7 = 8. Khi đó, a197 = 8. Khoa có q câu hỏi có dạng như sau: "Tổng các số từ phần tử thứ l đến phần từ thứ r của dãy A sau biến đổi là bao nhiêu?"

Yêu cầu: Em hãy giúp An lập trình để trả lời q câu hỏi của Khoa.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím):

• Dòng 1 chứa số nguyên dương q (1 ≤ q ≤ 100).

• q dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương l, r (1 ≤ l ≤ r ≤ 10^18).

Kết quả: q đòng, mỗi dòng chứa một số nguyên duy nhất là tổng các số tìm được.

Ví dụ:

Input:

2
9 13
44 45

Output:

19
17

Câu hỏi 1: l= 9, r = 13, a9 = 9, a10 = 1 + 0 = 1, a11 = 1 + 1 = 2, a12 = 1 + 2 = 3, a13 = 1 + 3 = 4

a9 + a10 + a11 + a12 + a13 = 9 +1 +2 +3 +4 = 19

Câu hỏi 2: l=44, r =45, a44 = 4 +4 = 8, a45 = 4 +5= 9

a44 + a45 = 8 + 9 = 17

Có 30% số điểm thỏả mãn: l ≤ 1 ≤r ≤9.

Có 30% số điểm thoa mãn: r - l ≤ 10^3.

Có 40% số điểm không có ràng buộc thêm.