题目描述

计算机生成并辅助的证明与验证在计算机科学领域中占据着一个小的分支领域。四色定理的第一个证明是在计算机程序的辅助下完成的，并且当前在验证方面的努力已经成功地验证了从高级代码到芯片级的转换。

这个问题涉及到计算与费马大定理的一部分相关的量：当$n > 2$时，方程$a^n + b^n = c^n$不存在整数解。

给定一个正整数$N$，你需要编写一个程序来计算两个量，这两个量与方程$x^2 + y^2 = z^2$的解有关，其中$x$、$y$和$z$被限制为小于等于$N$的正整数。你需要计算满足$x < y < z$且$x$、$y$、$z$互质（即它们没有大于$1$的公因数）的三元组$(x, y, z)$的数量。你还需要计算满足$0 < p \leq N$且$p$不属于任何三元组（不仅仅是互质的三元组）的数值$p$的数量。

输入

输入由一系列正整数组成，每行一个。输入文件中的每个整数都将小于等于$1000000$。输入以文件结束符结束。

输出

对于输入文件中的每个整数$N$，打印两个用空格分隔的整数。第一个整数是互质三元组的数量（使得三元组的每个分量都小于等于$N$）。第二个数是小于等于$N$的正整数中，不属于任何一个其分量都小于等于$N$的三元组的数的数量。对于每个输入行，都应该有一个对应的输出行。

输入示例

10
25
100

输出示例

1 4
4 9
16 27

来源

1991年杜克大学互联网编程竞赛，UVA 106