D. CGCDSSQ

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$a_{1}, ..., a_{n}$ бүхэл тоонуудын дараалал, мөн $q$ ширхэг $x_{1}, ..., x_{q}$ асуулт өгөгдсөн. $x_{i}$ асуулт бүрийн $1 ≤ l ≤ r ≤ n$ ба $gcd(a_{l}, a_{l + 1}, ..., a_{r}) = x_{i}$ байх $(l, r)$ хосын тоог тоолно.

бол $v_{1}, v_{2}, ..., v_{n}$-ий хамгийн их ерөнхий хуваагч ба бүх $v_{i}$-г хуваах хамгийн их бүхэл тоотой тэнцүү юм.

Оролт

Оролтын эхний мөрөнд дарааллын урт $n$, ($1 ≤ n ≤ 10^{5}$), дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоо $a_{1}, ..., a_{n}$, ($1 ≤ a_{i} ≤ 10^{9}$) байна.

Гуравдугаар мөрөнд асуултын тоо $q$, ($1 ≤ q ≤ 3 × 10^{5}$) байна. Дараагийн $q$ мөр бүр нь бүхэл тоо $x_{i}$, ($1 ≤ x_{i} ≤ 10^{9}$) байна.

Гаралт

Асуулт бүрийн хариултыг харгалзах мөрөнд хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3
2 6 3
5
1
2
3
4
6
Гаралт
1
2
2
0
1
Оролт
7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000
Гаралт
14
0
2
2
2
0
2
2
1
1
Сэтгэгдлүүдийг ачааллаж байна...