We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #233: Lattice points on a circle

Project Euler #233: Lattice points on a circle

This problem is a programming version of Problem 233 from projecteuler.net

Let be the number of points with integer coordinates that are on a circle passing through , , and .

It can be shown that .

Given two integers and , what is the number of all positive integers such that  ?

Input Format

The first line of each test file contains a single integer which is the number of queries.
Each of the next lines contains two space-separated integers and .

Constraints

  • .
  • is an odd squarefree integer.
  • In testfiles to :
    • .
    • .
  • In testfile and above:
    • .
    • when .
    • when .

Output Format

Print the answer to each query on a new line.

Sample Input 0

1
1000 1

Sample Output 0

433

Sample Input 1

1
100000000000 87

Sample Output 1

1

Explanation 1

The only integer less than such that is .

Sample Input 2

1
100000000000 31

Sample Output 2

3

Explanation 2

There exist only three integers such that : , and .