Вам дана последовательность целых чисел 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач