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.
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		//BufferedOutputStream bout=new BufferedOutputStream(System.out);
		int n=Integer.parseInt(br.readLine());
		int[] A=new int[n+1];
		A[0]=0;
		String[] s=br.readLine().split(" ");
		for(int i=1;i<=n;i++){
			A[i]=Integer.parseInt(s[i-1]);
		}
		Queries query=new Queries(n,A);
		StringBuilder sb=new StringBuilder("");
		int q=Integer.parseInt(br.readLine());
		int lim=(int)Math.sqrt(n);
		for(int i=0;i<q;i++){
			String[] t=br.readLine().split(" ");
			int p=Integer.parseInt(t[0]);
			int k=Integer.parseInt(t[1]);
			if(k<=lim){
				int res=query.f(p,k);
				//query.print(bout,res);
				//bout.write('\n');
				sb.append(res);
				sb.append('\n');
			}
			else{
				//System.out.println("got in");
				int res=query.doit(p,k);
				//query.print(bout,res);
				//bout.write('\n');
				sb.append(res);
				sb.append('\n');
			}
		}
		//query.print(bout,39393);
		//bout.close();
		System.out.print(sb);
	}
}

class Queries{
	int[] A; //size n+1
	int n;
	Map memo;
	int[][] dp=new int[100001][400];
	Queries(int N,int[] arr){
		n=N;
		A=arr;
		memo=new HashMap();
		int lim=(int)Math.sqrt(n);
		for(int p=1;p<=n;p++){
			for(int k=1;k<=lim;k++){
				dp[p][k]=-1;
			}
		}
	}
	
	int f(int p,int k){ //k<sqrt(n)
		if(p>n){return 0;}
		//long key=100001*(long)p+(long)k;
		int res=dp[p][k];
		/*if(memo.containsKey(key)){
			res=(int)memo.get(key);
			return res;
		}*/
		if(res!=-1){return res;}
		int p1=p+A[p]+k;
		res=1+f(p1,k);
		dp[p][k]=res;
		//memo.put(key,res);
		return res;
	}
	
	int doit(int p,int k){ //k>=sqrt(n)
		int res=0;
		int p1=p;
		while(p1<=n){
			p1=p1+A[p1]+k;
			res++;
		}
		return res;
	}
	
	void print(BufferedOutputStream bout,int res) throws IOException{ 
		int i=100000;
		while(res/i==0){
			i/=10;
		}
		while(i>0){
			int x=res/i;
			bout.write((char)((x%10)+'0'));
			i/=10;
		}
	}
}

