Stjepan gần đây đã nhận bằng cử nhân toán học từ Đại học Zagreb. Tất nhiên cha mẹ anh rất tự hào và đã quyết định tặng anh tất cả các số nguyên dương không lớn hơn ~2^{60}~. Để giữ chúng an toàn, anh nhanh chóng lưu tất cả các số đó vào một mảng ~A~ sao cho ~A_i = i~.

Người bạn ghen tị của anh, Martin, quyết định chơi khăm anh bằng cách thay thế liên tục phần tử của ~A~ bằng tổng các chứ số của nó cho đến khi tất cả các phần tử mảng ~A~ chỉ còn là số một chữ số. Ví dụ, giá trị ban đầu của phần tử thứ ~197~ là ~197~. Marin đầu tiên thay đổi giá trị đó thành ~1+9+7 = 17~ và sau đó thay đổi giá trị đó một lần nữa thành ~1 + 7 = 8~.

Stjepan rất buồn và cầu xin Marin trả lại mảng của anh về trạng thái ban đầu. Không may, Marin sẽ không làm điều đó cho đến khi Stjepan trả lời chính xác các truy vấn của anh ta: "Tổng các số từ phần tử thứ ~l~ đến phần tử thứ ~r~ của ~A~ là bao nhiêu?".

Hãy giúp Stjepan trả lời các truy vấn đó!.

Input

• Dòng đầu tiên chứa một số nguyên ~Q~ ~(1 \leq Q \leq 100)~ từ mô tả bài toán.
• ~Q~ dòng tiếp theo chứa hai số nguyên ~l_i~ và ~r_i~ ~(1 \leq l_i \leq r_i \leq 2^{60}~, là các tham số của truy vấn thứ ~i~ của Marin.

Output

In ra các câu trả lời cho mỗi truy vấn của Marin. Mỗi câu trả lời nên được in ra một dòng riêng và thứ tự của chúng phải khớp với thứ tự của các truy vấn như trong đầu vào.

Chú thích

• ~20 \%~ số điểm thỏa mãn ~1 \leq l_i \leq r_i \leq 9~.
• ~60 \%~ số điểm thỏa mãn ~r_i - l_i \leq 1000~.

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

Trong test đầ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~.
• ~A_9 + A_{10} + A_{11} + A_{12} + A_{13} = 9 + 1 + 2 + 3 + 4 = 19~.

Trong test thứ hai:

• ~A_{44} = 4 + 4 = 8~, ~A_{45} = 4 + 5 = 9~.
• ~A_{44} + A_{45} = 8 + 9 = 17~.