*a* is an array of *n* positive integers, all of which are not greater than *n*.

You have to process *q* queries to this array. Each query is represented by two numbers *p* and *k*. Several operations are performed in each query; each operation changes *p* to *p* + *a*<sub class="lower-index">*p*</sub> + *k*. There operations are applied until *p* becomes greater than *n*. The answer to the query is the number of performed operations.
The first line contains one integer *n* (1 ≤ *n* ≤ 100000).

The second line contains *n* integers — elements of *a* (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ *n* for each *i* from 1 to *n*).

The third line containts one integer *q* (1 ≤ *q* ≤ 100000).

Then *q* lines follow. Each line contains the values of *p* and *k* for corresponding query (1 ≤ *p*, *k* ≤ *n*).
Consider first example:

In first query after first operation *p* = 3, after second operation *p* = 5.

In next two queries *p* is greater than *n* after the first operation.
3
1 1 1
3
1 1
2 1
3 1
2
1
1
10
3 5 4 3 7 10 6 7 2 3
10
4 5
2 10
4 6
9 9
9 2
5 1
6 4
1 1
5 6
6 4
1
1
1
1
1
1
1
2
1
1
50
6 2 5 6 10 2 5 8 9 2 9 5 10 4 3 6 10 6 1 1 3 7 2 1 7 8 5 9 6 2 7 6 1 7 2 10 10 2 4 2 8 4 3 10 7 1 7 8 6 3
50
23 8
12 8
3 3
46 3
21 6
7 4
26 4
12 1
25 4
18 7
29 8
27 5
47 1
50 2
46 7
13 6
44 8
12 2
18 3
35 10
38 1
7 10
4 2
22 8
36 3
25 2
47 3
33 5
10 5
12 9
7 4
26 4
19 4
3 8
12 3
35 8
31 4
25 5
3 5
46 10
37 6
8 9
20 5
36 1
41 9
6 7
40 5
24 4
41 10
14 8
3
4
6
2
4
5
3
8
3
3
2
2
1
1
1
3
1
6
5
2
3
3
7
2
2
4
1
3
4
3
5
3
5
5
6
2
3
2
4
1
1
3
4
2
1
5
2
4
1
3
50
49 21 50 31 3 19 10 40 20 5 47 12 12 30 5 4 5 2 11 23 5 39 3 30 19 3 23 40 4 14 39 50 45 14 33 37 1 15 43 30 45 23 32 3 9 17 9 5 14 12
50
36 29
44 24
38 22
30 43
15 19
39 2
13 8
29 50
37 18
32 19
42 39
20 41
14 11
4 25
14 35
17 23
1 29
3 19
8 6
26 31
9 46
36 31
21 49
17 38
47 27
5 21
42 22
36 34
50 27
11 45
26 41
1 16
21 39
18 43
21 37
12 16
22 32
7 18
10 14
43 37
18 50
21 32
27 32
48 16
5 6
5 11
5 6
39 29
40 13
14 6
1
1
1
1
2
1
2
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
1
2
3
1
1
1
1
1
3
3
3
1
1
2
import sys
n = int(sys.stdin.readline())
list = [int(x) for x in sys.stdin.readline().split()]
master_list = []
for i in range(1,n):
    new_list = [0]* (n+1)
    for j in range(1,n+1):
        new_list[n-j] = new_list[min(n, (n-j) + list[(n-j)] + i)] + 1
    master_list.append(new_list)
print(master_list)
for _ in range(int(input())):
    p, k = [int(x) for x in input().split()]
    print(master_list[k-1][p-1])