Cho mảng ~a~ gồm ~2^{60}~ phần tử và ~a_i=i~ với mọi ~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~:

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

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

Input

• Dòng đầu tiên chứa số nguyên ~q~ ~(1 \le q \le 100)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ ~(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

15

Sample Input 2

2
9 13
44 45

Sample Output 2

19
17

Sample Input 3

1
1998 2018

Sample Output 3

102

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~l \le r \le 9~ với mọi truy vấn
• Subtask ~2~ với ~30\%~ số điểm: ~r-l \le 1000~ với mọi truy vấn
• Subtask ~3~ với ~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_{10}=1+0=1~, ~a_{11}=1+1=2~, ~a_{12}=1+2=3~, ~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_{45}=4+5=9~. Tổng ~a_{44}+a_{45}=8+9=17~.