Trong lúc chờ Tân loại bỏ bớt các hình dạng không hợp lý cho trò chơi oẳn tù tì, Lương và Định viết ra một con số đặc biệt: 2941999. Sau đó, hai bạn đã rủ Ngọc cùng ngồi giết thời gian bằng một trò chơi thú vị, ba bạn cùng cộng bình phương các chữ số của con số đặc biệt lại và lấy kết quả đó thay thế cho con số hiện tại: 2^2 + 9^ 2 + 4^2 + 1^2 + 9^2 + 9^2 + 9^2  = 345

Họ kiên trì lặp lại bước trên: 345->50->25->29->... cho tới khi nào được kết quả là số 1 thì dừng lại, vì cả ba đều rất ghét con số này (gợi lên sự lẻ loi của những chàng trai FA). Với tài năng toán học thiên bẩm, Ngọc nhận ra rằng nếu xuất phát từ con số 2941999 như trên thì không bao giờ biến đổi được nó về số 1 bằng cách lặp đi lặp lại bước cộng bình phương các chữ số. Lương và Định cũng công nhận điều này và hai bạn nhờ Ngọc xác định giúp xem có bao nhiêu con số đặc biệt như vậy (không thể biến đổi về số 1) trong đoạn các số tự nhiên từ L đến R.

Yêu cầu: Với từng cặp số tự nhiên L và R ( 1<=L<=R<=10^18), hãy giúp Ngọc xác định số lượng số đặc biệt nằm trong đoạn [L,R] .

Input: Vào từ file văn bản PEARL.INP:

• Dòng đầu chứa số nguyên dương T là số lượng câu hỏi của Lương và Định.
• Tiếp đến là T dòng, mỗi dòng chứa hai số tự nhiên L và R biểu thị câu hỏi tương ứng.

Output: Ghi ra file văn bản PEARL.OUT gồm T dòng, mỗi dòng chứa một số nguyên
duy nhất là câu trả lời cho câu hỏi tương ứng.

Ví dụ:

• Có 20% số test ứng với 20% số điểm của bài có T<=30 và R-L<=10^6 .
• Có 20% số test khác ứng với 20% số điểm của bài có T<=100 và 1<=L<=R<=10^9
• 60% số test còn lại ứng với 60% số điểm của bài có T<=100 .