PhuocThien cậu ta là \(1\) coder tinh nghịch cậu ta đã nghĩ ra \(1\) bài như sau:
Cho số nguyên dương \(n\) và hàm \(UX(n)\) được biểu diễn như sau:

int tcs(long long N) {
  long long sum = 0;
  do {
    sum += N % 10;
    N /= 10;
  } while(N);
  return sum;
}

int UX(long long N) {
  if(N > 10) return UX(tcs(N));
  else return N;
}

Input

• Dòng \(1\): Gồm \(1\) số nguyên dương \(Q\) là số truy vấn của bài toán. \((1 \le Q \le 10^6)\)
• \(Q\) dòng tiếp theo mỗi dòng gồm \(2\) số nguyên dương \(l\) và \(r\). \((1 \le l \le r \le 10^6)\)

Output

• Với mỗi truy vấn in ra số lượng giá trị làm PhuocThien hài lòng.

Example

5
10 17
4 9
100 1000
1 18
1 10000

0
1
100
2
1111