Cho ~T~ đoạn số nguyên dương ~[A; B]~. Trong mỗi đoạn, hãy tính tổng các số chính phương và đếm số lượng các số chính phương có tổng các ước là số nguyên tố.

Input

• Dòng đầu ghi số nguyên dương ~T~ (~1 \le T \le 10^6~) là số đoạn;

• ~T~ dòng tiếp theo, mỗi dòng ghi ~2~ số nguyên dương ~A, B~ (~1 \le 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ác ước là số nguyên tố trong đoạn ~[A; B]~ tương ứng.

Scoring

Cách chấm:

• Nếu tất cả các giá trị thứ nhất đúng: được ~50\%~ số điểm của test;

• Nếu tất cả các giá trị thứ hai đúng: được ~50\%~ số điểm của test.

Sample Input 1

1
1 20

Sample Output 1

30 3

Sample Input 2

2
20 40
2 10

Sample Output 2

61 1
13 2

Notes

Test 1:

• Đ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ố chính phương có tổng các ước là số nguyên tố.

Test 2:

• Đoạn ~[20; 40]~ gồm các số chính phương là: ~25, 36~ nên tổng là ~61~. Số ~25~ có tổng ước là ~31~, số ~36~ có tổng ước là ~91~ nên ta có ~1~ số thỏa mãn điều kiện.
• Đoạn ~[2; 10]~ gồm các số chính phương là: ~4, 9~ nên tổng là ~13~. Số ~4~ có tổng ước là ~7~, số ~9~ có tổng ước là ~13~ nên ta có ~2~ số thỏa mãn điều kiện.