解説

この問題は、「素因数分解」「鳩ノ巣原理」を利用して解くことができます。

数列 $A$ が区間 $[L,R]$ において「pairwise coprime」であるとは、
「任意の素数 $p$ に対して、$A_L$ $, \ldots ,$ $A_R$ の中に $p$ の倍数は高々$1$個である」と同値です。
（$p$ の倍数が複数あれば、それらの $\mathrm{gcd}$ は $p$ の倍数となり、「pairwise coprime」ではなくなる。
また、「pairwise coprime」でなければ、$\mathrm{gcd}(A_i, A_j)>1$ となる $A_i$ 、$A_j$ はともに $\mathrm{gcd}(A_i, A_j)$ の素因数の倍数になる。）

よって、数列 $A$ の各要素を素因数分解し、区間 $[L,R]$ において（異なる要素に）重複する素因数があるかを調べれば良いです。
実装では、map などを用いて各素数に番号を割り振ると良いです。

素因数分解は、各整数 $O(\sqrt A_{i})$ で行うことができます。
（エラトステネスの篩を用いた方法により、前処理 $O(A_{\max} \log \log A_{\max})$、各整数 $O(\log A_i)$ で行うことも出来ます。）

また、$2 \leq A_i$ より各整数は $1$ 個以上の素因数を持ちます。数列 $A$ に含まれる素因数の種類数を $w$ とすると、
鳩ノ巣原理より、長さが $w$ を超える区間では必ず素因数が重複します。
重複が発生した時点でクエリの探索を終了することで、各クエリ $O(w)$ で処理することができます。
$A_i \leq 10^4$ であるため、 $w$ は最大でも $1229$ です。

全体として、「各要素の素因数分解」「各素数へ番号の割り振り」「各クエリの処理」を行うため、
$O(N\sqrt A_{\max}+w\log w+Qw)$ で問題を解くことが出来ます。

---

この問題の解法や原案の一部は mts さんの協力によるものです。ありがとうございます。