Đề bài

Trí tuệ là một thuộc tính quan trọng của con người. Trong cuộc thi sắc đẹp phải là người đẹp và có khả năng ứng xử tốt. Trong phần thi ứng xử năm nay, thí sinh dự thi phải tính nhẩm các con số, để tính nhẩm tốt thì người đó phải là người có trí nhớ tốt, khả năng tính toán nhanh và phải có kiến thức toán học đủ sâu.

Ứng cử viên cho chức hoa hậu năm nay nhận được ~n~ cặp số (~a_i, b_i~), mỗi số có không quá 18 chữ số thập phân, ~0 < a_i \leq b_i~, ~i = 1 \dots n~. Với mỗi số nguyên trong đoạn ~[a_i, b_i]~ phải thay thế nó bằng tổng các chữ số của số đó. Nếu số nhận được có nhiều hơn một chữ số thì lại thay thế theo cách đã nêu cho đến khi nhận được số có một chữ số.

Hãy xác định tổng các số nhận được từ các số trong mỗi khoảng đã cho. Thí sinh đã trả lời đúng tất cả!

Input

Dữ liệu vào từ file MENTAL.INP:

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 100~).
• ~n~ dòng tiếp theo chứa 2 số nguyên ~a_i~ và ~b_i~ (~0 < a_i \leq b_i \leq 10^{18}~).

Output

Ghi vào file văn bản MENTAL.OUT các kết quả nhận được, mỗi kết quả trên một dòng.

Ví dụ

Sample Input

3
2 6
8 12
2000 2020

Sample Output

20
23
99

Giới hạn

• Thời gian: 1.0 giây
• Bộ nhớ: 256.0 MB
• 50% số điểm của bài ứng với ~n \leq 50; 1 < a_i \leq b_i \leq 10^4~.
• 30% số điểm của bài ứng với ~1 < a_i \leq b_i \leq 10^8~.
• 20% số điểm của bài không ràng buộc gì thêm (~n \leq 100; 1 < a_i \leq b_i \leq 10^{18}~).

Ghi chú (nếu có)

Số thu được cuối cùng của một số ~x~ sau khi thực hiện quy tắc trên chính là giá trị của ~x \pmod 9~ (nếu ~x \pmod 9 = 0~ thì giá trị là 9).