题目描述

给定长度为 $n$ 的数组 $a$。定义函数 $f(k,a,l,r)$ 如下：

ans := 0
for i from l to r:
    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$，表示测试组数。

每组测试数据第一行包含两个整数 $n,q$。下一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。接下来 $q$ 行，每行包含三个整数 $k,l,r$。

输出格式

对于每个询问，输出一行答案。

样例

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

5
6
1629
13
12
520

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 10^5$
• $1 \le q \le 5\cdot 10^4$
• $2 \le a_i \le 10^5$
• $1 \le k \le 10^5$
• $1 \le l \le r \le n$
• 所有测试组的 $n$ 之和不超过 $10^5$，所有测试组的 $q$ 之和不超过 $5\cdot 10^4$

来源

Codeforces Round 1017 (Div. 4), Problem H - La Vaca Saturno Saturnita