{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level. \r\u003cbr\u003eThis problem deals with computing quantities relating to part of Fermat\u0027s Last Theorem: that there are no integer solutions of a^n + b^n \u003d c^n for n \u0026gt; 2. \r\u003cbr\u003eGiven a positive integer N, you are to write a program that computes two quantities regarding the solution of x^2 + y^2 \u003d z^2, where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x \u0026lt; y \u0026lt; z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values 0 \u0026lt; p \u0026lt;\u003d N such that p is not part of any triple (not just relatively prime triples). \r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file"}},{"title":"Output","value":{"format":"HTML","content":"For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is \u0026lt;\u003dN). The second number is the number of positive integers \u0026lt;\u003dN that are not part of any triple whose components are all \u0026lt;\u003dN. There should be one output line for each input line. "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n25\r\n100\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4\r\n4 9\r\n16 27\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}