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ố?

Input

• 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)~.

Output

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.

Scoring

Mỗi dòng kết quả ghi đủ ~2~ kết quả, mỗi kết quả đúng được ~50\%~ điểm của test.

Sample Input 1

1
1 20

Sample Output 1

30 3

Notes

Đ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ố.