Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.

In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l and r (1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si). 

After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.

In order to choose the best sequence, Mole gives you t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.

Input

The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony. 

The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 109), the strengths of the ants. 

The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases. 

Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.

Output

Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [li, ri].

Examples

Input

5
1 3 2 4 2
4
1 5
2 5
3 5
4 5


Output

4
4
1
1

Note

In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.

In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.

In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.

In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class F474 {
	static final int inf = ((int) 1e9) + 100;

	public static int GCD(int a, int b) {
		if (b == 0)
			return a;
		return GCD(b, a % b);
	}

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = in.nextInt();
		int N = 1;
		while (N < n)
			N <<= 1;
		int[] arr = new int[N + 1];
		Arrays.fill(arr, inf);
		for (int i = 1; i <= n; i++) {
			arr[i] = in.nextInt();
		}

		SegmentTree st = new SegmentTree(arr);
		int q = in.nextInt();
		while (q-- > 0) {
			int i = in.nextInt();
			int j = in.nextInt();
			Trio t = st.query(i, j);
			int ans = j - i + 1;
			if (t != null && t.min == t.gcd)
				ans -= t.occ;
			// System.out.println(t.min + " " + t.gcd + " " + t.occ);
			sb.append(ans).append("\n");
		}
		System.out.print(sb);

	}

	static class Trio {
		int min, gcd, occ;

		Trio(int a, int b, int c) {
			min = a;
			gcd = b;
			occ = c;

		}
	}

	static class SegmentTree {
		int N;
		Trio[] sTree;
		int[] arr;

		SegmentTree(int[] in) {
			arr = in;
			N = in.length - 1;
			sTree = new Trio[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) {
			if (b == e) {
				if (arr[b] != inf)
					sTree[node] = new Trio(arr[b], arr[b], 1);
			} else {
				build(node << 1, b, (b + e) / 2);
				build((node << 1) + 1, (b + e) / 2 + 1, e);
				sTree[node] = merge(sTree[node << 1], sTree[(node << 1) + 1]);
			}
		}

		static Trio merge(Trio t1, Trio t2) {
			if (t1 == null && t2 == null)
				return null;
			if (t1 == null)
				return new Trio(t2.min, t2.gcd, t2.occ);
			if (t2 == null)
				return new Trio(t1.min, t1.gcd, t1.occ);
			int min = Math.min(t1.min, t2.min);
			int occ = 0;
			if (t1.min == min)
				occ += t1.occ;
			if (t2.min == min)
				occ += t2.occ;
			return new Trio(min, GCD(t1.gcd, t2.gcd), occ);
		}

		public Trio query(int i, int j) {
			return query(1, 1, N, i, j);
		}

		public Trio query(int node, int b, int e, int i, int j) {
			if (i > e || j < b)
				return null;
			if (b >= i && e <= j)
				return sTree[node];
			Trio q1 = query(node << 1, b, (b + e) / 2, i, j);
			Trio q2 = query((node << 1) + 1, (b + e) / 2 + 1, e, i, j);
			return merge(q1, q2);
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

}
