PYTRIP2 - Pythagorean triples (medium)


Pythagoras is credited, by tradition, for the first proof of the relation a2 + b2 = c2 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 , a2 + b2 = c2.
{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 2017-02-11, 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: 2014-04-04 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!
--ans(Francky)--> Your input method is correct, your program is too slow for now, you have to improve it. Good luck.

Last edit: 2014-04-04 18:26:00
Tomislav Gudlek: 2014-04-03 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: 2014-04-02 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,
cheers,
Alex

Filip: 2014-04-02 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: 2014-04-02 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: 2014-04-02 23:04:57

WE WANT SUBMIT BUTTON BACK!
--ans(Francky)--> You're allowed to try without shouting, and add 'please'.

Last edit: 2014-04-02 22:22:28
Filip: 2014-04-02 23:04:57

@Francky, are you ok?
Two guys and I have solved this problem together for competition. We are team. What is problem? This task is part of BubbleCup competition.If i know how to solve problem,I'll solve it.

Last edit: 2014-04-02 21:26:51
Francky: 2014-04-02 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.
The problem will be available in the future.
@teacher : I can understand it's a team work, but in this case, only one account should make submissions for each team. Thanks for your comprehension. Try to explain to students, thanks for that.

Last edit: 2014-04-02 15:36:39

Added by:Francky
Date:2013-04-11
Time limit:1s-3.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64