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 static java.math.BigInteger.*;

import java.util.*;

public class E {

	public E () {
		int N = sc.nextInt();
		int [] A = sc.nextInts();
		int Q = sc.nextInt();
		int [][] B = sc.nextInts(Q);

		long H = probablePrime(27, new Random()).longValue();
		HashMap<Long, Integer> G = new HashMap<>();

		int [][] Z = new int [N+1][];
		{
			@SuppressWarnings("unchecked")
			TreeSet<Integer> [] L = new TreeSet[N+1];
			for (int [] b : B) {
				int P = b[0], K = b[1];
				if (L[K] == null)
					L[K] = new TreeSet<>();
				L[K].add(P);
			}
			for (int K : req(N))
				if (L[K] != null)
					Z[K] = pri(L[K].toArray(new Integer[0]));
		}

		{
			int [] V = new int [N+1];
			int [] X = new int [N+1];
			int [] Y = new int [N+1];

			for (int K : req(N))
				if (Z[K] != null) {
					int [] M = Z[K];
					int VC = 0, XC = 0;
					for (int P : M)
						X[XC++] = P;
					while (XC > 0) {
						int P = X[XC-1], P2 = P + A[P-1] + K;
						if (P2 > N) {
							--XC; Y[P] = 1;
							V[VC++] = P;
						}
						else if (Y[P2] > 0) {
							--XC; Y[P] = Y[P2] + 1;
							V[VC++] = P;
						}
						else
							X[XC++] = P2;
					}
					for (int P : M)
						G.put(H * K + P, Y[P]);

					for (int i : rep(VC))
						Y[V[i]] = 0;
				}
		}

		for (int [] b : B) {
			int res = G.get(H * b[1] + b[0]);
			print(res);
		}
	}

	private static int [] pri(Integer [] A) { int [] res = new int [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static int [] rep(int N) { return rep(0, N); }
	private static int [] rep(int S, int T) { if (T <= S) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static int [] req(int N) { return req(0, N); }
	private static int [] req(int S, int T) { return rep(S, T+1); }
	////////////////////////////////////////////////////////////////////////////////////
	private final static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static void print (Object o, Object ... A) { IOUtils.print(o, A); }
	private static class IOUtils {
		public static class MyScanner {
			public String next() { newLine(); return line[index++]; }
			public int nextInt() { return Integer.parseInt(next()); }
			public String nextLine() { line = null; return readLine(); }
			public String [] nextStrings() { return split(nextLine()); }
			public int [] nextInts() {
				String [] L = nextStrings();
				int [] res = new int [L.length];
				for (int i = 0; i < L.length; ++i)
					res[i] = Integer.parseInt(L[i]);
				return res;
			}
			public int [][] nextInts (int N) {
				int [][] res = new int [N][];
				for (int i = 0; i < N; ++i)
					res[i] = nextInts();
				return res;
			}
			//////////////////////////////////////////////
			private boolean eol() { return index == line.length; }
			private String readLine() {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine() {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split(String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build(Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim(String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static void start() { if (t == 0) t = millis(); }
		private static void append(StringBuilder b, Object o, String delim) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					append(b, java.lang.reflect.Array.get(o, i), delim);
			} else if (o instanceof Iterable<?>)
				for (Object p : (Iterable<?>) o)
					append(b, p, delim);
			else {
				if (o instanceof Double)
					o = new java.text.DecimalFormat("#.############").format(o);
				b.append(delim).append(o);
			}
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print(Object o, Object ... A) { pw.println(build(o, A)); }
		private static void err(Object o, Object ... A) { System.err.println(build(o, A)); }
		private static void exit() {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(IOUtils.time());
			System.exit(0);
		}
		private static long t;
		private static long millis() { return System.currentTimeMillis(); }
		private static String time() { return "Time: " + (millis() - t) / 1000.0; }
	}
	public static void main (String[] args) { new E(); IOUtils.exit(); }
}
