Xét dãy ~A~ với ~a_i=i~. Mỗi phần tử được thay liên tục bằng tổng các chữ số của nó cho đến khi chỉ còn một chữ số.

Với mỗi truy vấn ~l,r~, cần tính tổng các phần tử từ ~l~ đến ~r~ sau khi biến đổi.

Input

• Dòng đầu 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 là đáp án cho truy vấn tương ứng.

Subtask

• Subtask ~1~ có ~30\%~ số điểm: ~1 \le l \le r \le 9~.
• Subtask ~2~ có ~30\%~ số điểm: ~r-l \le 10^3~.
• Subtask ~3~ có ~40\%~ số điểm: không có ràng buộc gì thêm.

Ví dụ

2
9 13
44 45

19
17