显然先考虑把每个 \(a_i\) 只因数分解，令 \(S(x)\) 表示 \(x\) 只因子的集合。
令 \(S_{l,r}=S\left(\prod\limits_{i=l}^ra_i\right)=S(a_l)\cup S(a_{l+1})\cup\cdots \cup S(a_r)\)。假如我们快速求出了 \(S_{l,r}\)：
\[\begin{aligned}\text{ans}&=\sum\limits_{i=1}^C[\gcd(i,\prod\limits_{k=l}^ra_k)=1]\\&=\sum\limits_{i=1}^C[S(i)\cap S_{l,r}=\varnothing]\end{aligned}
\]
考虑容斥，钦定 \(T\) 为 \(S_{l,r}\) 的子集，\(T\) 中的数都为 \(i\) 的只因子。具体地，设 \(f_S\) 表示 \(S\) 集合恰为 \(i\) 的只因子集合的方案数，\(g_S\) 表示 \(S\) 集合为 \(i\) 的只因子集合的子集的方案数（也就是钦定 \(S\) 中的数为只因子，其余任意），\(S\subseteq S_{l,r}\)：
\[g_S=\sum\limits_{S\subseteq T}f_T
\]
\[f_{S}=\sum\limits_{S\subseteq T}(-1)^{|T|-|S|}g_T
\]
我们要求 \(f_{\varnothing}\)：
\[\text{ans}=f_{\varnothing}=\sum\limits_{T\subseteq S_{l,r}}(-1)^{|T|}g_T
\]
\[\because \ g_T=\left\lfloor\frac{C}{\prod\limits_{i\in T}i}\right\rfloor
\]
\[\therefore\ \text{ans}=\sum\limits_{T\subseteq S_{l,r}}(-1)^{|T|}\left\lfloor\frac{C}{\prod\limits_{i\in T}i}\right\rfloor
\]
对 \(T\) 中的只因子 \(i\in S_{l,r}\) 根号分治：
- \(i\le \sqrt C\)，直接记忆化枚举 \(2^{\pi(\sqrt c)}\) 种情况即可，不难发现满足 \(\prod\limits_{i\in T}i\le C\) 的 \(T\) 不多，加点减枝卡一卡就行了。
- \(i>\sqrt C\)，不难发现一个 \(T\) 中至多含有一个这样的 \(i\)，也就是说剩下的全是 \(i\le \sqrt C\) 的只因子。于是只需要单独处理一个 \(i>\sqrt C\) 的所有倍数的贡献。即 \(-\sum\limits_{i>\sqrt C}\left\lfloor\frac{C}{i}\right\rfloor\)。但是这样做还有个小问题。在 \(i\le \sqrt C\) 的时候我们已经计算过了 \(i>\sqrt C,i\in T\) 的贡献，于是我们应该钦定 \(\left\lfloor\frac{C}{i}\right\rfloor\) 个数中只能计算 \(\nexists\ i\in S_{l,r},i\le \sqrt C,i\nmid j\) 的 \(j\) 的贡献。
注意到 \(i>\sqrt C\) 时 \(\left\lfloor\frac{C}{i}\right\rfloor\le \sqrt C\)，直接莫队维护所有的 \(i>\sqrt C\)，然后开个桶每次询问 \(O(\sqrt C)\) 暴力跑即可。
复杂度 \(O(q(\sqrt n+\sqrt C)+2^{\pi(\sqrt C)})\)，但是后面那个根本卡不满。
// Problem: Burenka, an Array and Queries
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1718F
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define i128 __int128
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), putchar('-');
if (x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
const int N = 1e5 + 100;
const int B = 350;
const int K = 100;
int n, len, b, c, m, ct;
int a[N], vs[B], pr[B], s[K][N], ans[N], t[N], tc[B], vis[B];
map<i128, int> S;
vector<int> fac;
i128 st;
struct qr {
int l, r, id;
qr () { }
qr (int _l, int _r, int _id) : l(_l), r(_r), id(_id) { }
bool operator < (const qr &rhs) const {
// if (l / len == rhs.l / len) return ((l / len) & 1) ? (r > rhs.r) : (r < rhs.r);
// return l / len < rhs.l / len;
return (l / len == rhs.l / len) ? r < rhs.r : (l / len < rhs.l / len);
}
} q[N];
void init(int lim) {
for (int i = 2; i <= lim; i++) {
if (!vs[i]) pr[++ct] = i;
for (int j = 1; j <= ct && i * pr[j] <= lim; j++) {
vs[i * pr[j]] = 1;
if (i % pr[j] == 0) break;
}
}
}
void add(int x) {
if (a[x] == 1) return;
if (!t[a[x]]) tc[c / a[x]]++; t[a[x]]++;
}
void del(int x) {
if (a[x] == 1) return;
if (t[a[x]] == 1) tc[c / a[x]]--; t[a[x]]--;
}
int dfs(int dep, int vl, int op) {
if (dep == fac.size()) return c / vl * op;
int res = 0;
if (fac[dep] <= c / vl) res += dfs(dep + 1, fac[dep] * vl, -op);
res += dfs(dep + 1, vl, op);
return res;
}
signed main() {
n = rd(), rd(), c = rd(), m = rd();
init(b = 320), len = n / sqrt(m);
for (int i = 1; i <= n; i++) {
a[i] = rd();
for (int j = 1; j <= ct; j++) {
if (a[i] % pr[j]) continue;
s[j][i]++;
while (a[i] % pr[j] == 0) a[i] /= pr[j];
}
}
for (int i = 1; i <= ct; i++)
for (int j = 1; j <= n; j++)
s[i][j] += s[i][j - 1];
for (int i = 1, l, r; i <= m; i++)
l = rd(), r = rd(), q[i] = qr(l, r, i);
sort(q + 1, q + m + 1);
for (int i = 1, l = 1, r = 0; i <= m; i++) {
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
while (l < q[i].l) del(l++);
while (r > q[i].r) del(r--);
int res = st = 0;
for (int j = 1; j <= b; j++) vis[j] = 1;
fac.clear();
for (int j = 1; j <= ct; j++) {
if (s[j][r] - s[j][l - 1]) {
for (int k = pr[j]; k <= b; k += pr[j]) vis[k] = 0;
st |= (((i128)1) << (j - 1));
fac.pb(pr[j]);
}
}
if (S.find(st) != S.end()) res = S[st];
else res = S[st] = dfs(0, 1, 1);
for (int j = 1; j <= b; j++)
vis[j] += vis[j - 1], res -= tc[j] * vis[j];
ans[q[i].id] = res;
}
for (int i = 1; i <= m; i++)
wr(ans[i]), pc('\n');
return 0;
}