D. CGCDSSQ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вам дана последовательность целых чисел a1, ..., an и q запросов x1, ..., xq. Для каждого запроса xi требуется подсчитать количество пар (l, r), таких, что 1 ≤ l ≤ r ≤ n и .

По определению — это наибольший общий делитель v1, v2, ..., vn, то есть наибольшее целое число, которое делит каждое vi.

Входные данные

В первой строке записано целое число n, (1 ≤ n ≤ 105), означающее длину последовательности. В следующей строке записано через пробел n целых чисел a1, ..., an, (1 ≤ ai ≤ 109).

В третьей строке записано целое число q, (1 ≤ q ≤ 3 × 105) — количество запросов. Затем следует q строк, в каждой строке записано целое число xi, (1 ≤ xi ≤ 109).

Выходные данные

Для каждого запроса выведите результат в отдельной строке.

Примеры
Входные данные
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