Условие:
Настроение Ля Вака Сатурно Сатурниты зависит от массива a
длины n
, значение которого известно только ей, и функции f(k,a,l,r)
, которую она знает, как вычислить.
Ниже представлен псевдокод функции f(k,a,l,r)
.
function f(k, a, l, r):
ans := 0
for i from l to r (inclusive):
while k is divisible by a[i]:
k := k/a[i]
ans := ans + k
return ans
Вам даны q
запросов, каждый из которых содержит целые числа k
, l
и r
. Для каждого запроса выведите f(k,a,l,r)
.
Входные данные
Первая строка содержит целое число t
(1≤t≤104
) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа n
и q
(1≤n≤105,1≤q≤5⋅104
).
Следующая строка содержит n
целых чисел a1,a2,…,an
(2≤ai≤105
).
Следующие q
строк каждая содержат три целых числа k
, l
и r
(1≤k≤105,1≤l≤r≤n
).
Гарантируется, что сумма n
не превышает 105
по всем наборам входных данных, и сумма q
не превышает 5⋅104
по всем наборам входных данных.
Выходные данные
Для каждого запроса выведите ответ в отдельной строке.