H. La Vaca Saturno Saturnitatime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputSaturnita's mood depends on an array $$$a$$$ of length $$$n$$$, which only he knows the meaning of, and a function $$$f(k, a, l, r)$$$, which only he knows how to compute. Shown below is the pseudocode for his function $$$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 ansYou are given $$$q$$$ queries, each containing integers $$$k$$$, $$$l$$$, and $$$r$$$. For each query, please output $$$f(k,a,l,r)$$$.InputThe first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 10^5, 1 \leq q \leq 5\cdot 10^4$$$).The following line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$2 \leq a_i \leq 10^5$$$).The following $$$q$$$ lines each contain three integers $$$k$$$, $$$l$$$, and $$$r$$$ ($$$1 \leq k \leq 10^5, 1 \leq l \leq r \leq n$$$).It is guaranteed that the sum of $$$n$$$ does not exceed $$$10^5$$$ over all test cases, and the sum of $$$q$$$ does not exceed $$$5\cdot 10^4$$$ over all test cases.OutputFor each query, output the answer on a new line.ExampleInput25 32 3 5 7 112 1 52 2 42310 1 54 318 12 8 9216 1 248 2 482944 1 4Output5 6 1629 13 12 520