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.


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

hide comments
2014-04-02 23:04:57 Francky
some submissions disqualified ; Filip, Vladimir Milenkovic, Irfan Smajevic, muhamed_ikovic@hotmail.com : please try with your own code.

Last edit: 2014-04-02 15:17:36
2014-04-02 23:04:57 Dzejlan
can you look at my code id=11373860
getting WA but it work. What is problem? Thanks.
--ans(Francky)--> You have some few errors, you should build a brute force to find small wrong cases. Good luck.

Last edit: 2014-04-02 00:32:54
2014-04-02 23:04:57 Lovro Puzar
I believe the constraint T * M < 10^8 is wrong. A passing solution with the addition of assert(T * M < 100000000) trips the assert. Perhaps the author meant sum(M) < 10^8.
--ans(Francky)--> It's true, it is T×M < 1.21×10^8 (there's two such cases), I'll edit the description. Congratulations to all the team ; you all made a great job. Hope you've found the task instructive.

Last edit: 2014-04-01 19:57:04
2014-04-02 23:04:57 Prodigy
for ??? ..output ???
--ans--> No other test cases are provided, you have to build them. Good luck.

Last edit: 2013-05-16 06:08:09
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.