Mảng lớn · CODER HUSC

Time limit: 1.0 s
Memory limit: 256 MB
Points: 100partial
AC rate: 36.0%
Solvers: 15

Cho mảng $a$ ~a~ gồm $2^{60}$ ~2^{60}~ phần tử và $a_i=i$ ~a_i=i~ với mọi $1 \le i \le 2^{60}$ ~1 \le i \le 2^{60}~. Tiến hành thực hiện thao tác sau với mỗi phần tử $a_i$ ~a_i~:

Liên tục thay đổi giá trị $a_i$ ~a_i~ thành tổng các chữ số của nó cho đến khi $a_i$ ~a_i~ chỉ có một chữ số. Ví dụ với $a_{197}=197$ ~a_{197}=197~, đầu tiên $a_{197}=1+9+7=17$ ~a_{197}=1+9+7=17~ và sau đó $a_{197}=1+7=8$ ~a_{197}=1+7=8~.

Cho $q$ ~q~ truy vấn, mỗi truy vấn yêu cầu tính tổng $a_l+a_{l+1}+...+a_r$ ~a_l+a_{l+1}+...+a_r~.

Input

Dòng đầu tiên chứa số nguyên $q$ ~q~ $(1 \le q \le 100)$ ~(1 \le q \le 100)~.
$q$ ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ ~l~ và $r$ ~r~ $(1 \le l \le r \le 2^{60})$ ~(1 \le l \le r \le 2^{60})~ mô tả truy vấn.

Output

Với mỗi truy vấn, in ra tổng cần tính trên một dòng.

Samples

Sample Input 1

1
1 5

Sample Output 1

Sample Input 2

2
9 13
44 45

Sample Output 2

19
17

Sample Input 3

1
1998 2018

Sample Output 3

Scoring

Subtask $1$ ~1~ với $30\%$ ~30\%~ số điểm: $l \le r \le 9$ ~l \le r \le 9~ với mọi truy vấn
Subtask $2$ ~2~ với $30\%$ ~30\%~ số điểm: $r-l \le 1000$ ~r-l \le 1000~ với mọi truy vấn
Subtask $3$ ~3~ với $40\%$ ~40\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

Trong ví dụ thứ hai,

Ở truy vấn đầu tiên, $a_9=9$ ~a_9=9~, $a_{10}=1+0=1$ ~a_{10}=1+0=1~, $a_{11}=1+1=2$ ~a_{11}=1+1=2~, $a_{12}=1+2=3$ ~a_{12}=1+2=3~, $a_{13}=1+3=4$ ~a_{13}=1+3=4~. Tổng $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_{44}=4+4=8~, $a_{45}=4+5=9$ ~a_{45}=4+5=9~. Tổng $a_{44}+a_{45}=8+9=17$ ~a_{44}+a_{45}=8+9=17~.