PITYFERM - Pitagoras y Fermat

no tags 

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.

This problem deals with computing quantities relating to part of Fermat's Last Theorem: that there are no integer solutions of a^n + b^n = c^n for n > 2.

Given a positive integer N, you are to write a program that computes two quantities regarding the solution of x^2 + y^2 = 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<y< 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 < p < N such that p is not part of any triple (not just relatively prime triples).

Input

The input consists of a sequence of positive integers, one per line. The first one is the number of test cases. Each following integer in the input file represents N and will be less than or equal to 1,000,000.

Output

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 <= N). The second number is the number of positive integers <= N that are not part of any triple whose components are all <=N . There should be one output line for each input line.

Example

Input:
3
10
25
100

Output:
1 4
4 9
16 27


Added by:Coach UTN FRSF
Date:2009-09-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:uva