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 \leq 10^6)\) là số đoạn;
• \(T\) dòng tiếp theo ghi 2 số nguyên dương \(A\), \(B\) \((A \leq B \leq 10^6)\).

Output

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

Example

1
1 20

30 3

2
1 6
2 10

5 1
13 2

Scoring

• Subtask \(1\): có \(20\) test (\(50\%\)), tương ứng \(4{,}0\) điểm với \(T = 1\) và \(A \leq B \leq 10^3\);
• Subtask \(2\): có \(12\) test (\(30\%\)), tương ứng \(2{,}4\) điểm với \(T \leq 10^3\) và \(A \leq B \leq 10^3\);
• Subtask \(3\): có \(8\) test (\(20\%\)), tương ứng \(1{,}6\) điểm không có ràng buộc nào thêm.