408540: GYM103182 I Number Spiral

You take a piece of paper and, from the middle of the page, you start completing a counter clock-wise number spiral, with $$$1$$$ as a starting point. After reaching $$$49$$$, you see that you ended up with a complete spiral with a side of $$$7$$$.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

Interestingly, you notice that a lot of the prime numbers are occurring on the diagonals. For no particular reason, you start wondering how many prime numbers there are on the bottom left diagonal, i.e. from the center of the spiral to its bottom left corner. In the example above, note that the numbers in question are $$$1$$$, $$$7$$$, $$$21$$$, $$$43$$$.

The first line consists of:

• An odd integer $$$N$$$ ($$$3 \leq N \leq 10^6 + 1$$$), the max side length of the spiral;
• An odd integer $$$S$$$ ($$$1 \leq S \leq 10^7 + 1$$$), the starting point of the spiral - by starting point, we refer to the value in the center of the spiral;
• An integer $$$Q$$$ ($$$1 \leq Q \leq 10^6$$$), the number of queries.

Then, there are $$$Q$$$ lines containing two odd integers $$$a$$$ and $$$b$$$ ($$$3 \leq a < b \leq N$$$) representing the query "How many prime numbers are there on the bottom left diagonal between the spirals with the sides of a and b (inclusive)?". For example, in your original spiral, for $$$a = 3$$$, $$$b = 7$$$, the numbers are $$$7$$$, $$$21$$$, $$$43$$$.

The output should contain $$$Q$$$ lines, the answer to each query.

7 1 1
3 7

2

7 10000001 1
3 7

0