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.