Pythagoras is credited, by tradition, for the first proof of the relation a² + b² = c² 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, i.e., a² + b² = c².

{3, 4, 5} is the most common example of such a triple.

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⁸

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 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

< Previous 1 2 Next >
	Francky: 2014-04-02 23:04:57 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
	Dzejlan: 2014-04-02 23:04:57 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
	Lovro Puzar: 2014-04-02 23:04:57 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
	Prodigy: 2014-04-02 23:04:57 for ??? ..output ??? --ans--> No other test cases are provided, you have to build them. Good luck. Last edit: 2013-05-16 06:08:09