PYTRIP - Bitogoras Number

no tags 

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.

hide comments
AsMaNjAs: 2014-04-15 19:43:20

@killerz: Check the output for 2nd case.It should be 1 instead of 2.

killerz: 2013-04-13 19:27:28

This problem has been rejudged since I have added up the better input files for this problem. I apologize for that to all the users who have submitted the solution previously. Sorry for all


Special thanks to Francky for showing up the patients for me and guidance


Added by:killerz
Date:2013-04-09
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own