This is the easy version of the problem. In this version, it is guaranteed that $r=l+k-1$ for all queries.

For an arbitrary array $b$, Yunli can perform the following operation any number of times:

• Select an index $i$. Set $b_i = x$ where $x$ is any integer she desires ($x$ is not limited to the interval $[1,n]$).

Denote $f(b)$ as the minimum number of operations she needs to perform until there exists a consecutive subarray$^{\text{∗}}$ of length at least $k$ in $b$.

Yunli is given an array $a$ of size $n$ and asks you $q$ queries. In each query, you must output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$. Note that in this version, you are only required to output $f([a_l, a_{l+1}, \ldots, a_{l+k-1}])$.

Input

The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains three integers $n$, $k$, and $q$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$) — the length of the array, the length of the consecutive subarray, and the number of queries.

The following line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$).

The following $q$ lines contain two integers $l$ and $r$ ($1 \leq l \leq r \leq n$, $r=l+k-1$) — the bounds of the query.

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$.

Output

Output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$ for each query on a new line.

见题面 Input 部分

见题面 Output 部分

In the first query of the first testcase, $b=[1,2,3,2,1]$. Yunli can make a consecutive subarray of length $5$ in $2$ moves:

• Set $b_4=4$
• Set $b_5=5$

In the second query of the first testcase, $b=[2,3,2,1,2]$. Yunli can make a consecutive subarray of length $5$ in $3$ moves:

• Set $b_3=0$
• Set $b_2=-1$
• Set $b_1=-2$