题目描述

对于任意数组 b，云璃可以执行任意次以下操作：

• 选择一个下标 i，把 bᵢ 改成她想要的任意整数 x（x 不限于 [1, n]）。

记 f(b) 为使 b 中存在一个长度至少为 k 的连续子数组所需的最少操作次数。

连续子数组：若存在从下标 i 开始、长度为 k 的子数组，满足对所有 i < j ≤ i+k−1 都有 bⱼ = bⱼ₋₁ + 1。

云璃拿到一个长度为 n 的数组 a，并会提出 q 个询问。每个询问中，你需要输出：

$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \dots, a_j])$$

输入格式

第一行包含一个整数 t（1 ≤ t ≤ 10⁴）——测试数据的组数。

每组测试数据的第一行包含三个整数 n, k, q（1 ≤ k ≤ n ≤ 2×10⁵，1 ≤ q ≤ 2×10⁵）——数组长度、连续子数组长度、询问个数。

接下来一行包含 n 个整数 a₁, a₂, ..., aₙ（1 ≤ aᵢ ≤ n）。

接下来 q 行，每行两个整数 l, r（1 ≤ l ≤ r ≤ n，且保证 r ≥ l + k − 1）。

保证所有测试数据的 n 之和不超过 2×10⁵，所有测试数据的 q 之和不超过 2×10⁵。

输出格式

对每个询问，在新的一行输出其答案。

样例

输入：

3
7 5 3
1 2 3 2 1 2 3
1 7
2 7
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
1 5
5 4 2
4 5 1 2 3
1 4
1 5

输出：

6
5
2
2
5
2
3

说明：第一组测试数据的第二个询问中：

• f([2,3,2,1,2]) = 3，因为可以设 b₃=4, b₄=5, b₅=6，用 3 次操作得到一个长度为 5 的连续子数组；
• f([2,3,2,1,2,3]) = 2，因为可以设 b₃=0, b₂=−1，用 2 次操作得到一个从位置 2 开始的长度为 5 的连续子数组。

该询问答案为 3 + 2 = 5。

数据范围与子任务

• 对于 100% 的数据：1 ≤ t ≤ 10⁴，1 ≤ k ≤ n ≤ 2×10⁵，1 ≤ q ≤ 2×10⁵，1 ≤ aᵢ ≤ n；所有数据 n 之和、q 之和均 ≤ 2×10⁵。
• 所有询问满足 r ≥ l + k − 1。