PITPAIR - Pythagorean Legacy

It is necessary to find a minimal integer value R which is equal to the length of the hypotenuse (the side opposite the right angle) of N non-identical rectangular triangles with integer lengths of sides.

Input

t - number of test cases [t <= 100], than t lines follow, each line contains one integer - N, equal to the required number of different rectangular triangles. [1 <= N <= 2000]

Output

For each test case your program should output a number R in a separate line (R fits in a 64-bit integer), equal to the minimal integer value of a hypotenuse for which exactly N different rectangular triangles can be constructed; then in separate lines follow exactly N numbers equal to the shorter cathetus (side adjacent to the right angle) of each of the rectangular triangles, in ascending order.

Example

Input:
2
1
2

Output:
5
3
25
7
15

Added by:Roman Sol
Date:2005-03-01
Time limit:2.25s
Source limit:8192B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ZCon 2005

hide comments
2012-09-16 14:08:15 Tanmay
Should the hypotenuse be in exactly N distinct triangles or the value of hypotenuse should be such that it is least and it appears in at least N distinct triangles?
i.e. for N = 3, should we output 65 or 125? Because 125 is first hypotenuse to appear in exactly 3 triangles, but 65 is the least with at least 3 triangles (even though it appears in 4 distinct triangles, actually).

Last edit: 2012-09-16 14:09:04
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.