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à \(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

• 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 \(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.

Scoring

• Subtask 1 (\(20\%\) số điểm): \(T \le 30\) và \(R-L \le 10^6\).
• Subtask 2 (\(20\%\) số điểm): \(T \le 100\) và \(1 \le L \le R \le 10^9\).
• Subtask 3 (\(60\%\) số điểm): \(T \le 100\)

Example

1
2941999 2942002

3