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\).

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(Q\) là lượng câu hỏi
• \(Q\) cặp dòng tiếp theo:
  • Dòng thứ nhất chứa số nguyên dương \(l\)
  • Dòng thứ hai chứa số nguyên dương \(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

Example

2
1
2
1
9

0
1

Scoring

• \(50\%\) test có \(Q \leq 100\) và \(1 \leq l \leq r \leq 10^5\)
• \(50\%\) test có \(Q \leq 10^5\) và \(1 \leq l \leq r \leq 10^9\)