Hàm \(F(a)\) với \(a\) là một số nguyên dương được định nghĩa đệ quy như sau:

• Nếu \(a < 10, F(a) = a\).
• Nếu \(a > 9, F(a) = F\)(tổng các chữ số của a).

Ví dụ, \(F(91) = F(10) = 1\).

ami cần các bạn đếm số lượng số \(x\) trong đoạn \([l, r]\) mà \(F(x) = 9\).

Dễ dàng nhận thấy bài toán này có thể giải được bằng quy hoạch động chữ số cơ bản. Hãy thể hiện trình độ bản thân với ami nhé.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(Q\) là lượng câu hỏi.

• \(Q\) dòng tiếp theo chứa, mỗi dòng chứa 1 cặp số nguyên dương \(l, r\) biểu thị một đoạn.

Output

• \(Q\) dòng, mỗi dòng là số lượng số \(x\) tương ứng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(Q \leq 100\) và \(1\) \(\leq\) \(l\) \(\leq\) \(r\) \(\leq\) \(10^{5}\).

• Subtask \(1\) (\(50\%\) số điểm): \(Q \leq 10^{5}\) và \(1\) \(\leq\) \(l\) \(\leq\) \(r\) \(\leq\) \(10^{9}\).

Example

2
1 2
1 9 

0
1