PEARL - Số đặc biệt
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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: 22+92+42+12+92+92+92=345. Họ kiên trì lặp lại bước trên: 345→50→25→29→85→89→145→42… 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à  (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].

Dữ liệu vào 

- 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 LR biểu thị câu hỏi tương ứng.

Kết quả:

Ghi ra 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ụ

Input

1
2941999 2942002

Output

3

 

Ràng buộc:

- 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.  
- Có 60% số test còn lại ứng với 60% số điểm của bài có T≤100.

 


Nguồn: PREVNOI TEAM 20182019 Đà Nẵng

Back to Top