\(A_i\) は素因数分解して, 素因数ごとに累乗数を計算する. これの累積和を取っておく.

各クエリについては, \(P_i\) も素因数分解して, \([L_i, R_i]\) と比べてすべての素因数の累乗数が小さければ割り切れる. \(P_i\) に含まれる素因数うち \(2000\) 以下の素数だけ考えればいい.