I. Number Spiral
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

Input

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

Output

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

Examples
Input
7 1 1
3 7
Output
2
Input
7 10000001 1
3 7
Output
0