- All Contests
- ProjectEuler+
- Project Euler #216: Investigating the primality of numbers of the form 2n² - 1

# Project Euler #216: Investigating the primality of numbers of the form 2n² - 1

# Project Euler #216: Investigating the primality of numbers of the form 2n² - 1

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

Consider three integers , and where , and is not the square of an integer.

Let the second degree polynomial . In this challenge, we will be interested in the prime values of for integers .

E.g. with , and , the first such prime numbers are , , , , , and .

How many numbers are prime for ?

**Input Format**

The first line of each test case contains three space-separated integers , and .

The second line contains a single integer which is the number of queries.

Each of the next lines contains a value of .

**Constraints**

- .
- .
- .
- .
- and is not a perfect square.
- .

**Output Format**

Print the answer to each query in a new line.

**Sample Input 0**

```
2 0 -1
1
10
```

**Sample Output 0**

```
7
```

**Explanation 0**

The values of for are :

**Sample Input 1**

```
2 0 1
1
20
```

**Sample Output 1**

```
4
```

**Explanation 1**

The evaluation of for yields to :

**Sample Input 2**

```
1 0 1
1
13
```

**Sample Output 2**

```
5
```

**Explanation 2**

There exist prime numbers of the form where : .