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 + ap + k. There operations are applied until p becomes greater than n. The answer to the query is the number of performed operations.

Input

The first line contains one integer n (1 ≤ n ≤ 100000).

The second line contains n integers — elements of a (1 ≤ ai ≤ 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).

Output

Print q integers, ith integer must be equal to the answer to ith query.

Example

Input

3
1 1 1
3
1 1
2 1
3 1


Output

2
1
1

Note

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.
import java.util.*;
import java.io.*;
 
public class Main{ 
  public static int dp[][];
  public static int arr[], n;
  public static void main(String[] args)throws Exception {
    InputReader in = new InputReader(System.in);
    PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    n = in.nextInt();
 
    dp = new int[n+1][350];
    for(int i = 0; i <= n; i++){
      Arrays.fill(dp[i], -1);
    }
 
    arr = new int[n+1];
 
    for(int i = 1; i <= n; i++){
      arr[i] = in.nextInt();
    }
 
    int sqrt = (int) Math.sqrt(n);
 
    for(int i = n; i >= 1; i--){
      for(int j = 1; j <= sqrt; j++){
        solve(i, j);
      }
    }
 
    int q = in.nextInt();
    for(int i = 1; i <= q; i++){
      int p = in.nextInt(), k = in.nextInt();
      if(k <= sqrt)pw.println(dp[p][k]);
      else pw.println(bruteForce2(p, k));
    }
 
 
    pw.close();
  }
 
  static int solve(int x, int s){
    if(x > n) return 0;
    if(dp[x][s] != -1) return dp[x][s];
 
    int m = 1 +  solve(arr[x]+s+x, s);
 
    return dp[x][s] = m;
  }
 
  static int bruteForce2(int p, int k){
    int x = 0;
    while(p <= n){
      p = p + arr[p] + k;
      x++;
    }
    return x;
  }
 
  static int bruteforce(int p, int k){
    if(p > n) return 0;
 
    return 1 + bruteforce(arr[p] + p + k, k);
 
  }
 
  static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
 
        public int[] readIntArray(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }
 
        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;
 
                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }
 
                    if (this.numChars <= 0) {
                        return -1;
                    }
                }
 
                return this.buf[this.curChar++];
            }
        }
 
        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }
 
            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }
 
            int res = 0;
 
            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }
 
            throw new InputMismatchException();
        }
 
        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }
 
    }
}