Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$, denoting the host genome length and the number of genomic segments Isaac is interested in ($1 \le n, q \le 2 \cdot 10^5$).

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$, describing the host genome ($1 \le a_i \le n$).

Each of the following $q$ lines contains two integers $l$ and $r$, denoting the boundaries of a genomic segment for which the infection level should be estimated ($1 \le l \le r \le n$).

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