背景

YSGH 牛逼

题目描述

给定长度为 $n$ 的数组 $a$，$Q$ 次询问 $\operatorname{lcm}(a_l, a_{l + 1}, \ldots , a_{r - 1}, a_r)$。

由于输出较大，你只需要输出答案对 ${10}^9 + 7$ 取模的值。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行两个正整数 $n, Q$。

接下来 $n$ 行，第 $i$ 行一个正整数表示 $a_i$。

接下来 $Q$ 行，一行两个正整数 $l,r$（$1 \le l \le r \le n$），表示一次询问。

输出格式

对于每次询问，一行一个整数表示答案。

1
3 3
63
70
112
1 2
1 3
2 3

630
5040
560

提示

对于 $100\%$ 的数据，$1 \le n, Q, T \le 300$，$1 \le a_i \le 2^{60}$。