Настроение Ля Вака Сатурно Сатурниты зависит от массива `a` длины `n`, значение которого известно только ей, и функции `f(k, a, l, r)`, которую она знает, как вычислить. Ниже представлен псевдокод функции `f(k, a, l, r)`: ``` function f(k, a, l, r):

Настроение Ля Вака Сатурно Сатурниты зависит от массива 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≤10^4
) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа n
и q
(1≤n≤105,1≤q≤5⋅104
).

Следующая строка содержит n
целых чисел a1,a2,…,an
(2≤ai≤10^5
).

Следующие q
строк каждая содержат три целых числа k
, l
и r
(1≤k≤10^5,1≤l≤r≤n
).

Гарантируется, что сумма n
не превышает 10^5
по всем наборам входных данных, и сумма q
не превышает 5⋅10^4
по всем наборам входных данных.

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