Saturnita 的情绪取决于一个长度为 $$$n$$$ 的数组 $$$a$$$(只有他知道其含义)和一个只有他知道如何计算的函数 $$$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 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 10^5, 1 \leq q \leq 5\cdot 10^4$$$)。
以下行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$2 \leq a_i \leq 10^5$$$)。
以下 $$$q$$$ 行每行包含三个整数 $$$k$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \leq k \leq 10^5, 1 \leq l \leq r \leq n$$$)。
保证所有测试用例的$$$n$$$之和不超过$$$10^5$$$,所有测试用例的$$$q$$$之和不超过$$$5\cdot 10^4$$$。
输出
对于每个查询,在新行中输出答案。
示例
输入复制
25 32 3 5 7 112 1 52 2 42310 1 54 318 12 8 9216 1 248 2 482944 1 4
输出复制
5 6 1629 13 12 520