~Stjepan~ vừa nhận được bằng cử nhân toán từ đại học của ~Zagreb~. Đương nhiên, bố mẹ anh ấy rất tự hào về con của họ và quyết định tặng anh ấy tất cả số nguyên dương không lớn hơn ~2^{60}~ như một món quà.

Vì là người cẩn thận, để giữ quà của mình an toàn, Stjepan giữ chúng trong mảng ~A~, với ~A_i=i~. Vì ghen tỵ, nên Marin quyết định chơi khăm Stejpan bằng cách thay từng phần tử trong ~A~ bằng tổng chữ số phần tử đó.

Với mỗi phần tử, Marin sẽ thực hiện thao tác trên cho đến phần tử ấy chỉ còn một chữ số. Ví dụ, ban đầu số thứ ~197~ là ~197~, đầu tiên Marin thay ~197~ thành giá trị ~1 + 9 + 7 = 17~ và sau đó lại tiếp tục thay ~17~ thành ~1 + 7 = 8~.

Stjepan trầm cảm sau khi biết những món quà của mình bị Marin phá như vậy, anh yêu cầu Marin biến dãy ~A~ trở lại ban đầu. Vì sinh ra đã hống hách, nên Marin quyết không làm dãy trở lại bình thường trừ khi Stjepan trả lời đúng ~Q~ câu hỏi: "Tổng của các số từ vị trí ~l~ đến vị trí ~r~ trong dãy hiện tại là bao nhiêu?"

Input

Dòng đầu tiên gồm một số nguyên dương ~Q( 1 \le Q \le 100)~ là số câu hỏi của Marin. ~Q~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~l_i~ và ~r_i~ ~(1 \le l_i \le r_i \le 2^{60})~ , hai số trong câu hỏi của Marin.

Output

In ra câu trả lời cho từng câu trong Q câu hỏi của Marin. Mỗi câu trả lời được in trên một dòng theo đúng thứ tự nhập.

Phân bố điểm

Có một test, ứng với bộ câu hỏi có ~1 \le l_i \le r_i \le 9~.

Có ba test, ứng với bộ câu hỏi có ~r_i - l_i \le 1000~.

Examples

Sample input 1

1
1 5

Sample output 1

15

Sample input 2

2
9 13
44 45

Sample output 2

19
17

Sample input 3

1
1998 2018

Sample output 3

102

Giải thích ví dụ thứ 2:

-Ở câu hỏi đầu tiên: ~A_{9} = 9, A_{10} = 1 + 0 = 1, A_{11} = 1 + 1 = 2, A_{12} = 1 + 2 = 3, A_{13} = 1 + 3 = 4.~

Nên ~A_{9} + A_{10} + A_{11} + A_{12} + A_{13} = 9 + 1 + 2 + 3 + 4 = 19~.

-Ở câu hỏi thứ hai: ~A_{44} = 4 + 4 = 8, A_{45} = 4 + 5 = 9.~

Nên ~A_{44} + A_{45} = 8 + 9 = 17~.