У Ярослава есть массив p = p1, p2, ..., pn (1 ≤ pi ≤ n), состоящий из n различных целых чисел. Также есть m запросов:
- Запрос номер i представляется в виде пары целых чисел li, ri (1 ≤ li ≤ ri ≤ n).
- Ответом на запрос li, ri является количество пар целых чисел q, w (li ≤ q, w ≤ ri) таких, что pq является делителем pw.
Помогите Ярославу, ответьте на все его запросы.
Выходные данные
Выведите m целых чисел — ответы на запросы Ярослава в порядке их следования во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
1
1 1
|
1
|
|
2
|
10 9
1 2 3 4 5 6 7 8 9 10
1 10
2 9
3 8
4 7
5 6
2 2
9 10
5 10
4 10
|
27
14
8
4
2
1
2
7
9
|