Little John rất thích các số đối xứng (palindrome) và coi chúng là những con số "đẹp". Một số đối xứng là một số nguyên có giá trị không đổi khi đọc ngược hay đọc xuôi - ví dụ: 6, 11 và 121 là các số đối xứng, trong khi 10, 12, 223 và 2244 thì không (mặc dù 010=10, nhưng chúng ta không xét các chữ số 0 ở đầu khi xác định một số có phải là số đối xứng hay không).

Gần đây, cậu ấy cũng bắt đầu quan tâm đến các số chính phương và đưa ra định nghĩa về số vừa đẹp vừa phương (fair and square) - đó là một số vừa là số đối xứng, vừa là bình phương của một số đối xứng khác. Ví dụ, 1, 9 và 121 là các số vừa đẹp vừa phương (vì chúng là số đối xứng và lần lượt là bình phương của 1, 3 và 11), trong khi 16, 22 và 676 không phải là số vừa đẹp vừa phương: 16 không phải là số đối xứng, 22 không phải là số chính phương, và mặc dù 676 là số đối xứng và là số chính phương, nhưng nó là bình phương của 26, mà 26 không phải là số đối xứng.

Bây giờ cậu ấy muốn tìm kiếm các số vừa đẹp vừa phương lớn hơn. Nhiệm vụ của bạn là, cho trước một khoảng mà Little John đang tìm kiếm, hãy cho cậu ấy biết có bao nhiêu số vừa đẹp vừa phương trong khoảng đó để cậu ấy biết khi nào mình đã tìm thấy tất cả.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) - các điểm đầu mút của khoảng mà Little John đang xem xét.

Dữ liệu ra

Với mỗi bộ test, hãy xuất ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng số vừa đẹp vừa phương lớn hơn hoặc bằng \(A\) và nhỏ hơn hoặc bằng \(B\).

Ràng buộc

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1):
• \(1 \le T \le 100\).
• \(1 \le A \le B \le 1000\).
• Tập dữ liệu lớn thứ nhất (Test set 2):
• \(1 \le T \le 10000\).
• \(1 \le A \le B \le 10^{14}\).
• Tập dữ liệu lớn thứ hai (Test set 3):
• \(1 \le T \le 1000\).
• \(1 \le A \le B \le 10^{100}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
1 4
10 120
100 1000

Case #1: 2
Case #2: 0
Case #3: 2

Nguồn

Google Code Jam 2013, Vòng loại, bài Fair and Square.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.