Yuuki vừa nhận bằng cử nhân Toán học từ University Wollongong.Tất nhiên, bố mẹ anh ấy rất tự hào và đã quyết định tặng anh ấy tất cả các số nguyên dương không lớn hơn $2^{60}$ làm quà. Để giữ an toàn, anh ấy 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 ấy, Sora, quyết định chơi khăm anh bằng cách liên tục thay thế mỗi 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ử của $A$ chỉ còn một chữ số. Ví dụ, giá trị ban đầu của phần tử thứ 197 trong $A$ là 197. Sora lần đầ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$.

Yuuki rất buồn và cầu xin Sora trả lại mảng của anh ấy về trạng thái ban đầu. Không may là Sora sẽ không làm điều đó cho đến khi Yuuki trả lời đúng $Q$ truy vấn của anh ấy: “Tổng các số từ phần tử thứ $l$ đến phần tử thứ $r$ của $A$ là bao nhiêu?”.

Input:

• Dòng đầu tiên chứa một số nguyên $n$ ($1 \leq n \leq 100$) là số truy vấn từ mô tả bài toán.
• $Q$ dòng tiếp theo, mỗi dòng 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$.

Output:

• Xuất ra các câu trả lời cho từng truy vấn của Sora. Mỗi câu trả lời in trên một dòng riêng biệt và thứ tự của các câu trả lời phải khớp với thứ tự các truy vấn đã cho trong đầu vào.

Scoring:

• Trong các trường hợp kiểm tra có tổng điểm là 10 điểm, với mỗi truy vấn sẽ có $1 \leq l_i \leq r_i \leq 9$.

• Trong các trường hợp kiểm tra có tổng điểm là 30 điểm, với mỗi truy vấn sẽ có $r_i - l_i \leq 1000$.

Example:

1
1 5

 15

 2
 9 13
 44 45

 19
 17

1
1998 2018

102

Note:

Truy vấn thứ nhất: $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$.

Truy vấn thứ hai: $A[44] = 4 + 4 = 8$, $A[45] = 4 + 5 = 9$. $A[44] + A[45] = 8 + 9 = 17$.