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 , ie , a² + b² = c².
{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.