1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int t[100001];
map<int, ll> cnt, pre;

int main() {
    int N, Q;
	cin >> N >> Q;
	for (int i = 0; i < N; ++i) cin >> t[i];

	unordered_map<int, int> m;
	for (int i = N - 1; i >= 0; --i) {
		unordered_map<int, int> tmp;
		for (auto x : m) tmp[__gcd(t[i], x.f)] += x.s;
		++tmp[t[i]];
		swap(tmp, m);
		for (auto& x : m) cnt[x.f] += x.s;
	}
	for (auto& x : cnt) pre[x.f] = x.s + (pre.size() ? pre.rbegin()->s : 0);
	
	while (Q--) {
		int a, b;
		cin >> a >> b;
		auto ia = pre.upper_bound(a - 1), ib = pre.upper_bound(b);
		cout << (ib != pre.begin() ? prev(ib)->s : 0) - (ia != pre.begin() ? prev(ia)->s : 0) << '\n';
	}
}