Description

Given an array $a$ of length $n$, answer $Q$ queries of $\operatorname{lcm}(a_l, a_{l + 1}, \ldots , a_{r - 1}, a_r)$.

Since the output can be large, you only need to output the answer modulo ${10}^9 + 7$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case, the first line contains two positive integers $n, Q$.

In the next $n$ lines, the $i$-th line contains a positive integer $a_i$.

In the next $Q$ lines, each line contains two positive integers $l, r$ ($1 \le l \le r \le n$), representing one query.

Output Format

For each query, output one integer per line, representing the answer.

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

630
5040
560

Hint

For $100\%$ of the testdata, $1 \le n, Q, T \le 300$, $1 \le a_i \le 2^{60}$.

Translated by ChatGPT 5