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.

Loading...

- All Contests
- ProjectEuler+
- Project Euler #233: Lattice points on a circle

# 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 .