\(Q = 1\) の場合の解説です。

各 \(i\) \((1 \leq i \leq N)\) に対して、以下の操作を行います。

全ての \(A_i\) の素因数 \(x\) について、

このグラフ上で、\(S\) から \(T\) への最短経路をダイクストラ法を用いて求めれば良いです。

計算量は、\(O(N \log \max(A) \log( \log \max(A)) \log(N+ \max(A))) \) です。