#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

#define pii pair<int, int>

struct Fenwick {
	vector<int> v;
 
	Fenwick(int n) : v(n) {
	}
 
	void add(int i, int x) {
		for (int j = i; j < v.size(); j += j & -j) {
			v[j] += x;
		}
	}
 
	int sum(int i) {
		int x = 0;
		for (int j = i; j > 0; j -= j & -j) {
			x += v[j];
		}
		return x;
	}
};


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		vector<int> v(N + 1);
		for (int i = 1; i <= N; i++) {
			cin >> v[i];
		}
		vector<int> d(N + 1, 1);
		vector<int> e(N + 1);
		for (int i = 1; i <= N; i++) {
			while (i + d[i] <= N && v[i + d[i]] % (d[i] + 1) == 0) {
				d[i]++;
			}
			e[i + d[i] - 1]++;
		}
		Fenwick f(N + 1);
		for (int i = 1, s = 0; i <= N; i++) {
			s++;
			f.add(i, s);
			s -= e[i];
		}
		int Q;
		cin >> Q;
		vector<vector<pii>> w(N + 1);
		for (int i = 0; i < Q; i++) {
			int L, R;
			cin >> L >> R;
			w[L].push_back({R, i});
		}
		vector<int> ans(Q);
		for (int i = 1, s = 0, c = 0; i <= N; i++) {
			for (auto [j, q] : w[i]) {
				ans[q] = f.sum(j) - f.sum(i - 1);
			}
			for (int j = i + 1; j < i + d[i]; j++) {
				f.add(j, -1);
			}
			f.add(i + d[i], d[i] - 1);
		}
		for (int i = 0; i < Q; i++) {
			cout << ans[i] << '\n';
		}
	}
	return 0;
}