Niềm ham thích của Nam là được học về các con số và tính chất của nó. Trong toán học Nam đã hiểu rất rõ thế nào là số nguyên tố, số chính phương, số hoàn hảo, ước số, bội số... Để khơi gợi niềm đam mê và ham thích của Nam, thầy giáo đã giao cho Nam một số bài tập. Trong các bài tập đó có bài tập là: cho số chính phương ~M~, em hãy tính tổng các ước của ~M~ và cho biết tổng đó có là số nguyên tố hay không?

Yêu cầu: Cho hai số nguyên dương ~A~, ~B~. Hãy tính tổng các số chính phương trong đoạn ~[A; B]~ và số lượng các số chính phương trong đoạn đó có tổng ước là số nguyên tố?

Dữ liệu

Vào từ tệp văn bản CPNT.INP gồm:

• Dòng 1 ghi số nguyên dương ~T~ (~T \le 10^6~) là số đoạn;
• ~T~ dòng tiếp theo ghi 2 số nguyên dương ~A~, ~B~ (~A \le B \le 10^6~).

Kết quả

Ghi ra tệp văn bản CPNT.OUT gồm ~T~ dòng, mỗi dòng ghi tổng các số chính phương và số lượng số chính phương có tổng ước là số nguyên tố trong đoạn ~[A; B]~ tương ứng.

Ví dụ

Ví dụ 1

CPNT.INP

1
1 20

CPNT.OUT

30 3

Giải thích: Đoạn ~[1; 20]~ gồm các số chính phương là 1, 4, 9, 16 nên tổng là 30. Số 1 có tổng ước là 1, số 4 có tổng ước là 7, số 9 có tổng ước là 13, số 16 có tổng ước là 31 nên ta có 3 số nguyên tố.

Ví dụ 2

CPNT.INP

2
1 6
2 10

CPNT.OUT

5 1
13 2

Ghi chú: Mỗi dòng của tệp CPNT.OUT ghi đủ 2 kết quả, mỗi kết quả đúng được 50% điểm của test.

Giới hạn

• Subtask 1: có 50% test ứng với ~T = 1~ và ~A \le B \le 10^3~;
• Subtask 2: có 30% test ứng với ~T \le 10^3~ và ~A \le B \le 10^3~;
• Subtask 3: có 20% test không có ràng buộc nào thêm.