Housework

Peter’s housework is to implement the function below:

input: A,B,C,x positive integers
output: y
1.  y=1
2.  while x ≥ C
3.    y=y+1
4.    if x is odd
5.      x=Ax+B
6.    else
7.      x=floor(x/C)
8.    end
9.  end

He got some examples to test the function:

A=3, B=1, C=2
x=21 ⟶ 64 ⟶ 32 ⟶ 16 ⟶ 8 ⟶ 4 ⟶ 2 ⟶ 1, y=8
x=211 ⟶ 634 ⟶ 317 ⟶ 952 ⟶ 476 ⟶ ... ⟶ 16 ⟶ 8 ⟶ 4 ⟶ 2 ⟶ 1, y=40
x=123321 ⟶ 369964 ⟶ 184982 ⟶ 92491 ⟶ 277474 ⟶ ... ⟶ 16 ⟶ 8 ⟶ 4 ⟶ 2 ⟶ 1, y=75

A=15, B=5, C=10
x=21 ⟶ 320 ⟶ 32 ⟶ 3, y=4
x=211 ⟶ 3170 ⟶ 317 ⟶ 4760 ⟶ 476 ⟶ ... ⟶ 161 ⟶ 2420 ⟶ 242 ⟶ 24 ⟶ 2, y=16
x=123321 ⟶ 1849820 ⟶ 184982 ⟶ 18498 ⟶ 1849 ⟶ ... ⟶ 416 ⟶ 41 ⟶ 620 ⟶ 62 ⟶ 6, y=14

A=7, B=3, C=5
x=21 ⟶ 150 ⟶ 30 ⟶ 6 ⟶ 1, y=5
x=211 ⟶ 1480 ⟶ 296 ⟶ 59 ⟶ 416 ⟶ ... ⟶ 23 ⟶ 164 ⟶ 32 ⟶ 6 ⟶ 1, y=13
x=123321 ⟶ 863250 ⟶ 172650 ⟶ 34530 ⟶ 6906 ⟶ ... ⟶ 21 ⟶ 150 ⟶ 30 ⟶ 6 ⟶ 1, y=17

The function will be used as follows: Given numbers $A, B, C$ and $Q$ he has to compute the minimal and maximal value of the function across all elements of the closed intervals $[lo_{i},up_{i}]$ for $i=1,\ldots,Q$ . For example:

A=3, B=1, C=2
lo=10, up=100 ⟶ min_y=5, max_y=119
lo=100,up=1000 ⟶ min_y=8, max_y=179
lo=1000,up=10000 ⟶ min_y=11, max_y=262

A=15, B=5, C=10
lo=10,up=100 ⟶ min_y=2, max_y=15
lo=100,up=1000 ⟶ min_y=3, max_y=30
lo=1000,up=10000 ⟶ min_y=4, max_y=52

A=7, B=3, C=5
lo=10,up=100 ⟶ min_y=2, max_y=23
lo=100,up=1000 ⟶ min_y=3, max_y=40
lo=1000,up=10000 ⟶ min_y=5, max_y=48

Input specification

The first line contain the numbers $A,B,C$ . The second line contains the number $Q$ . Then $Q$ lines follow, each with 2 numbers $lo_{i}$ and $up_{i}$ . The numbers separated by spaces.

Output specification

$Q$ lines with the required numbers, separated by spaces.

Constraints

$1\le Q \le 100$
$1\le lo,up \le 1\_000\_000$
$1\le up-lo+1 \le 10\_000$
$1\le A,B,C \le 31$
We can be certain that the computed lengths are not larger that $1\_000$ and the intermediate computation results are fit into a 64-bit signed integer.