PYTRIP2  Pythagorean triples (medium)
Pythagoras is credited, by tradition, for the first proof of the relation a^{2} + b^{2} = c^{2} in any right angled triangle where c is hypotenuse and a and b are the catheti.
We define a Pythagorean triple as a set of three positive integers a, b, and c which satisfy the above equation , ie ,
a^{2} + b^{2} = c^{2}.
{3,4,5} is the most common example of such triples.
Input
The first line of input contains an integer T, the number of test cases.
Each of the next T lines contains two integers N, M.
Output
For each test case, print on a single line the number of Pythagorean triplet {a,b,c} such that N ≤ a,b,c ≤ M.
Example
Input: 3 1 5 4 10 10 100 Output: 1 1 45
Constraints
0 < T < 100 0 < N < M 0 < T × M < 1.21×10^8
There are several input files.
Time limit is ×20 my top speed with C language (1kB of code).
For your information, my total best time is 0.59s for the 6 input files. (Edit 20170211, after compiler changes).
Warning, it could be hard with interpreted languages.
You can try before the quite similar tutorial problem : PYTRIP before.
Information
This problem is part of the Bubble Cup competition qualification round (April 2014).
@students: good luck. GNU_salutations.
hide comments
Vukasin:
20140404 17:46:29
Can someone explain me how the input into my program is done? How server enters data into my program? I obviously have problem with that(I use scanf). Is scanf right choice, im writing in C programming language. Thanks!


Tomislav Gudlek:
20140403 03:45:49
Dudes. Even if you're solving problems together for Bubble Cup qualification round, there's no reason for submitting the same code here on SPOJ. A single user submitting is sufficient for getting credit. 

Aleksandar Kahriman:
20140402 23:04:57
Hi Francky, I understand your frustration, but please allow us to submit. There aren't too many teams anyway, so it shouldn't be a problem for you to manually ban people that are abusing the system (not that you should be wasting your time on that, but this is a rather big deal for the people who have spent a lot of time on this). Me and my team have spent around 6 hours on your problem, and the submit button vanished when we were about to submit our final solution. Hope you will reconsider,


Filip:
20140402 23:04:57
@Francky bubblecup.org BubbleCup is competition by MDCS(Microsoft Development Center Serbia) and this is first quals for final. Every year they choose randomly SPOJ problems for qual. Do you want to make problem for all contestants and organizers? Please remove your problem from SPOJ if you doesn't want to anybody solve it. We have solved correctly this problem. 

Francky:
20140402 23:04:57
I didn't knew about this competition, it could have been fine if organizer send me a message. If my problem suit well for that task, I'm quite happy. But I'm not allowing copy/paste submissions for this problem (one team > one account) ; there were some troubles. Moreover, I prefer that this 'competition' hosts it's own data and judge. So my problem will be unavailable until the end of this 'competition'. Thanks for your comprehension. 

popina:
20140402 23:04:57
WE WANT SUBMIT BUTTON BACK!


Filip:
20140402 23:04:57
@Francky, are you ok?


Francky:
20140402 23:04:57
Submissions disallowed for a while. There's a pollution with some copy/paste solution. Filip : don't try to insist anymore. Please be respectful for users who earn points.

Added by:  Francky 
Date:  20130411 
Time limit:  1s3.400s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 