Вам дана последовательность целых чисел a1, ..., an и q запросов x1, ..., xq. Для каждого запроса xi требуется подсчитать количество пар (l, r), таких, что 1 ≤ l ≤ r ≤ n и 
.
По определению 
— это наибольший общий делитель v1, v2, ..., vn, то есть наибольшее целое число, которое делит каждое vi.
Выходные данные
Для каждого запроса выведите результат в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 6 3
5
1
2
3
4
6
|
1
2
2
0
1
|
|
2
|
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
|