CF2094H La Vaca Saturno Saturnita

Saturnita'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 ans


```
```

You are given $ q $ queries, each containing integers $ k $ , $ l $ , and $ r $ . For each query, please output $ f(k,a,l,r) $ .
                            

The 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.

For each query, output the answer on a new line.