SPOJ.com - Problem WPC5A

WPC5A - Structures

no tags

In the Galactical Wars happens the great event of designing a structure to honour the current generation of participants. (It is another matter that inevitably the monument is destroyed at the end of the Galactical Wars).

The organizers this year do not believe that this is a good event, and have reduced the event to building a right structure: a right-angled triangle that represents the geometry of the universe. Further they have given a specific odd integer n, which they want one of the shorter sides of the triangle to be.

The organizers in the galaxy H2 are infuriated with this high-handedness. To demonstrate their prowess in this event, they have decided to build all possible right structures. Calculate how many different right structures they can possibly build.

Input

First line contains a single integer T, denoting the number of test cases.

T lines follow, each containing an odd integer ’n’ denoting the given size of a side.

Output

T lines, each containing a single integer denoting the number of ways to form a right angled triangle with one of the smaller sides as ’n’.

Constraints

1 ≤ T ≤ 10

1 ≤ n ≤ 10¹²

n is odd.

Example

Input:
1
3

Output:
1

Explanation

There exists only 1 right angled triangle with sides 3, 4, 5.

Submit solution!

hide comments



	Francky: 2015-02-22 02:38:17 The number of psolver is very curious : here higher than CATHETEN which is easier !!! So we can't rely on number of AC ; it's only an indication. = In fact, there's HOMEW, COMDIV and PSYCO* that possibly share a common idea, and probably many others. The science for put a problem in tutorial/classical isn't exact. (and a bit boring). = I'm not so against put this one back to classical, but data is very poor ; I would hope psolver search for more quality in description, constraints and data... = I do like democratic expression, and I prefer count my voice only in case of tie, so here I'll move back to classical, and encourage psolvers to give their opinion with good justifications as wisfaq did. = In any problem, a good comment will be appreciate for its value. I encourage any comment that will increase quality in the problem set and the care of psolvers. +wisfaq+ Thanks, Francky. Last edit: 2015-02-22 10:27:03
	wisfaq: 2015-02-21 21:46:13 Francky, if about a year after publication a problem doesn't have more than 55 sols it definitely doesn't belong to tutorial. The fact that the testcases don't contain pseudo-P numbers is pretty irrelevant. My algoritm runs in 0.04 sec in Pascal without making any assumptions about the nature of the testcases. You're thinking too much from the point of fast f**** Is it too much asked to revert this problem to classical? There are more "duplicates" in SPOJ, is that a problem? Please think about those that solved it in the meantime and loose the points earned all of a sudden without warning. Last edit: 2015-02-21 22:00:08**
	numerix: 2015-02-21 13:03:44 As the problemsetter of that "new" problem PTC I want to explain my position: When I published PTC I knew WPC5A, but missed CATHETEN for a reason I don't know. After publishing and the first AC submission to PTC I realized that CATHETEN exists and PTC only differs in different description and different constraints. I'm sorry about that. Now, what to do: I don't think removing PTC is a good idea. There are some AC submissions so far and I don't think that the correct approach is too obvious. On the other hand I agree with wisfaq that moving problems to tutorial section that stayed in classical for a long time should be avoided, except that the problem has so many solvers that it does not result in a measurable loss of points. As there are only 55 users with AC submission for WPC5A, it should not be moved to tutorial section. (Francky) => I think it's not only a matter of constraints. Here test cases are weak without strong-pseudo-P numbers. This problem was published one year after CATHETEN, and I didn't check it at that time, I should have move it to tutorial at publication time. EB try to do their best. Sorry about that. When I published CATHETEN, I thought to set constraints a bit higher, but I choose lower ones to focus on the main problem. Now I think PTC is good one, when considering an approach without fully f***** input. So It's OK for me to keep PTC in classical ; only for that reason. Else I would have moved it too. Last edit: 2015-02-21 13:18:57**
	wisfaq: 2015-02-20 21:30:21 I don't agree with moving problems that have been around for a long time to tutorial just because of the fact that a new one has been published with "much better constraints". The new one has nothing to do with the problem as such but with fast f*****. In fact there are a many problems on SPOJ that are about fast f***. So I'm in doubt if that new problem adds anything to SPOJ. Perhaps it were better if that new problem was simply removed. (Francky) => I've took this decision because one can solve this problem without f***, and then we need a good is_p**, and I think there's few good problems for that ; and I plan a specific problem to help users for that. I hope you understand that. I agree that, without that point, new problems shouldn't be extension of a simple task with a common harder task. +wisfaq+ Nevertheless, one shouldn't move a problem to tutorial because about a year later a problem is published with "better constraints". That's unfair to those that solved the problem then. If a problem deserves to be in tutorial then it should be moved there as fast as possible. Not about a year later. (Francky) => Right, we need to do that as quickly as possible. I remember I probably (not sure) saw that problem and hesitate to move it. I should have done that earlier. It's possible some problems hadn't been fully checked and maybe some need to moved, or modified... we're trying to do the best. ++wisfaq++ So? (Francky) => So, this one is a decent tutorial for PTC. Don't you think ? +++wisfaq+++ PTC has his own tutorial, didn't you see it? (Francky) => Yes, this one can help too. Last edit: 2015-02-20 22:44:37**
	Francky: 2015-02-20 15:45:19 @mehmetin : Yes, CATHETEN. This problem should now be put in tutorial, as PTC have much better constraints for this 'range'.
	mehmetin: 2014-05-07 16:10:51 Wasn't there a similar problem?
	[Rampage] Blue.Mary: 2014-05-07 08:37:18 The problem means "n is not the longest side of the triangle", doesn't mean "n is the shortest side of the triangle".
	Bhavik: 2014-04-01 15:19:57 @triveni: thank you for answering my previous query , i will try again:) EDIT:AC Last edit: 2014-04-01 16:04:28
	Bhavik: 2014-04-01 11:07:16 @triveni:can you look at my id:11369529 and tell if i need to optimize or need better complexity than what i have implemented..though i am not sure why it gives tle on first thought!! thank you ans-> complexity seems fine. Last edit: 2014-04-01 15:09:38

Submit solution!

Added by:	triveni
Date:	2014-03-29
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	ACA judge IITK, WPC5