FIND HYPOTENUSE

Problem code: QCJ4

Alice and Bob are returning home from their math class. The teacher was discussing Pythagoras' Theorem in class. All of a suddden Alice came up with an intriguing question. He asked Alice what would be the hypotenuse of least length of exactly N distinct right triangles. Alice who was not quite as sharp as Bob said, "I don't quite understand the question. What do you mean by N distinct triangles?" Bob explained, "Suppose N = 2 and you choose a certain hypotenuse. You should be able to construct exactly 2 distinct right triangles with that hypotenuse such that all sides(including hypotenuse) are integral. The answer you must give me is the smallest length the hypotenuse can have. In this case it turns out to be 25 and the sides are (7,24) (15,20)".

Now As usual your task is to help Alice with the solution.

Input

First line will contain T, the number of test cases. Then T( T<1000) lines follow on each line the number N (1<=N<=3000) will be given.

Output

Output must contain exactly T lines, the minimum length of the hypotenuse for each test case. Note: Output may not fit in a 64 bit integer

Example

Input:
2
1
2


Output:
5
25

Author: abhijith
Date Added: 27-01-2010
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

This is almost the same as

suh_ash2008 @ 31 Jan 2010 06:49 PM

This is almost the same as the problem https://www.spoj.pl/problems/PITPAIR/

SUCCESSFUL SUBMISSIONS


Fetching successful submissions