Root Value — Eolymp

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains two integers $n, q$ ( $1 \leq n, q \leq 2 \cdot 1 0^{5}$ 1\le n,q \le 2\cdot 10^5) — the length of array $a$ and the number of queries respectively.

The second line of each test case contains $n$ integers $a_{1}, a_{2}, ..., a_{n}$ a_1 , a_2 , ... , a_n ( $2 \leq a_{i} \leq 200$ 2 \le a_i \le 200) — the array $a$ .

Then $q$ lines follow, each line contains two integers $l, r$ ( $1 \leq l \leq r \leq n$ 1 \le l \le r \le n) — boundaries of the desired query.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases does not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Output

For each query, print a single integer , the value of the range.

Examples

Example 1

Loading

Note

In the first test case. When $l = 1$ l=1 , $r = 4$ r = 4

$3 \times 3 \times 3 \times 3 = 81$ 3\times 3\times 3 \times 3 = 81 , $481 = 3$ \sqrt[4]{81} = 3 so $f (81) = 4$ f(81) = 4

Scoring

Subtask $1$ ( $10$ points): $\sum n, \sum q \leq 5000$ \sum n , \sum q \le 5000 , for each query $a_{l} \times a_{l + 1} \times ... \times a_{r} \leq 1 0^{12}$ a_{l} \times a_{l+1} \times ... \times a_r \le 10^{12} .
Subtask $2$ ( $20$ points): $\sum n, \sum q \leq 5000$ \sum n , \sum q \le 5000.
Subtask $3$ ( $30$ points): $a_{1} = a_{2} = ... = a_{n}$ a_1 = a_2 = ... = a_n.
Subtask $4$ ( $90$ points): No additional constraints.