H. La Vaca Saturno Saturnita
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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)$$$.

Input

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.

Output

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

Example
Input
2
5 3
2 3 5 7 11
2 1 5
2 2 4
2310 1 5
4 3
18 12 8 9
216 1 2
48 2 4
82944 1 4
Output
5
6
1629
13
12
520