By Pythagoras Theorem c * c = a * a + b * b is property of right angled triangle where 'c' is hypotenuse and 'a' and 'b' are the other two sides. With this, there are Pythagoras triplet sets of three positive integers {a, b, c} which satisfy the above equation.

For example if a = 3, b = 4, c = 5. c * c = a * a + b * b thus the set {3, 4, 5} is a Pythagoras triplet.

Impressed by the great discovery our friends Kickky and Bickky researched and found the numbers of such triplets within a range.

Thus you will be given a range of 'n' and 'm' which you may assume as different values of 'c' in given equation. You have to see if any Pythagoras Triplet exist for it where 'a' and 'b' must be positive and smaller than 'c'. Display the number of such triplets within the range inclusively which we call as "Bitogoras Number".

Input

Input start with number of test cases 't', 1 <= t <= 100.

Each case consist of two numbers 'n' and 'm'.

Constraints

1 <= n <= 50000

1 <= m <= 50000

1 <= a < c

1 <= b < c

n <= c <= m

n < m

Output

Output the number of triplets within the range 'n' and 'm' inclusively for each test case.

Example

Input:
3
1 5
4 10
10 100

Output:
1
2
51

Explanation for Test Case 1

• Range is 1 to 5.
• for c = 1 no such pair of 'a' and 'b' exist.
• for c = 2 no such pair of 'a' and 'b' exist.
• for c = 3 no such pair of 'a' and 'b' exist.
• for c = 4 no such pair of 'a' and 'b' exist.
• for c = 5, 5 * 5 = 3 * 3 + 4 * 4.
• thus the answer is 1.

Explanation for Test Case 2

• Range is 4 to 10.
• Possible triplets are:
  1. c = 5: 5 * 5 = 3 * 3 + 4 * 4
  2. c = 10: 10 * 10 = 6 * 6 + 8 * 8
• Thus the answer is 2.