An và Khoa rất thích chơi với dãy số. Hôm nay, Khoa đã nêu bài toán như sau:

Cho dãy ~A~ gồm ~n~ số nguyên ~a_1,a_2,\dots,a_n~. Ban đầu, ~a_i~ được gán bằng ~i~ ~(1 \le i \le n \le 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ế một phần tử 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 ~a_{197} = 197~. Khoa lần lượt biến đổi giá trị của ~a_{197}~ như sau: ~197 = 1 + 9 + 7 = 17~, tiếp tục biến đổi ~17 = 1 + 7 = 8~. Khi đó ~a_{197} = 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?

INPUT

Dòng 1 chứa số nguyên dương ~q~ ~(1 \le q \le 100)~. ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l, r~ ~(1 \le l \le r \le 10^{18})~.

OUTPUT

In ra ~q~ dòng, mỗi dòng chứa một số nguyên — đáp án cho mỗi truy vấn tương ứng: tổng các giá trị của ~a_l, a_{l+1}, \dots, a_r~ sau khi đã biến đổi.

SAMPLE INPUT

2
9 13
44 45

SAMPLE OUTPUT

19
17

GIẢI THÍCH

• Với truy vấn 1: các giá trị sau biến đổi của ~a_9,a_{10},a_{11},a_{12},a_{13}~ lần lượt là ~9,1,2,3,4~. Tổng = 19.
• Với truy vấn 2: ~a_{44}=8, a_{45}=9~. Tổng = 17.

SUBTASKS