問題文

長さ$N$の整数列$A$が与えられます。 この整数列のどの2つの要素も互いに異なります。

$Q$個のクエリが与えられます。各クエリでは、3つの整数$X,L,R$が与えられるので、 次の問題を解いてください。

• 問題：$A_L, A_{L+1}, \cdots, A_R$のうち、$X$で割り切れるものの個数を求めて下さい。

制約

$1\leq N \leq 5\times 10^5$
$1\leq A_i \leq 5\times 10^5$
$1\leq Q \leq 5\times 10^5$
$1\leq X \leq 5\times 10^5$
$1\leq L \leq R \leq N$
$A_i \neq A_j (i \neq j)$

入力

$N$
$A_1 \ A_2 \ \cdots A_N$
$Q$
$X_1 \ L_1 \ R_1$
$X_2 \ L_2 \ R_2$
$\cdots$
$X_Q \ L_Q \ R_Q$

出力

$ans_1\\ ans_2\\ \cdots\\ ans_Q$

サンプル

8
2 3 5 6 7 9 11 4
3
1 1 8
2 4 8
3 3 7

8
2
2