```go
package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

func nextInt(data []byte, p *int) int {
	n := len(data)
	i := *p
	for i < n && (data[i] < '0' || data[i] > '9') && data[i] != '-' {
		i++
	}
	sign := 1
	if data[i] == '-' {
		sign = -1
		i++
	}
	val := 0
	for i < n && data[i] >= '0' && data[i] <= '9' {
		val = val*10 + int(data[i]-'0')
		i++
	}
	*p = i
	return val * sign
}

func bitAdd(bit []int64, n, idx int, val int64) {
	for idx <= n {
		bit[idx] += val
		idx += idx & -idx
	}
}

func addLeft(bitA, bitB []int64, n, i, p int, coeff int64) {
	end1 := p + 1
	c1 := coeff * int64(i-p)
	bitAdd(bitB, n, 1, c1)
	bitAdd(bitB, n, end1+1, -c1)
	l2 := end1 + 1
	if l2 <= i {
		alpha := -coeff
		beta := coeff * int64(i+1)
		bitAdd(bitA, n, l2, alpha)
		bitAdd(bitA, n, i+1, -alpha)
		bitAdd(bitB, n, l2, beta)
		bitAdd(bitB, n, i+1, -beta)
	}
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0
	t := nextInt(data, &p)

	out := make([]byte, 0, 1<<20)

	for ; t > 0; t-- {
		n := nextInt(data, &p)
		k := nextInt(data, &p)
		q := nextInt(data, &p)

		cidx := make([]int, n+1)
		for i := 1; i <= n; i++ {
			v := nextInt(data, &p)
			cidx[i] = v - i + n
		}

		m := n - k + 1
		cnt := make([]int, 2*n+2)
		freq := make([]int, k+2)
		B := make([]int, m+1)

		maxFreq := 0
		for i := 1; i <= k; i++ {
			id := cidx[i]
			old := cnt[id]
			if old > 0 {
				freq[old]--
			}
			old++
			cnt[id] = old
			freq[old]++
			if old > maxFreq {
				maxFreq = old
			}
		}
		B[1] = maxFreq
		for s := 2; s <= m; s++ {
			id := cidx[s-1]
			old := cnt[id]
			freq[old]--
			old--
			cnt[id] = old
			if old > 0 {
				freq[old]++
			}
			for maxFreq > 0 && freq[maxFreq] == 0 {
				maxFreq--
			}

			id = cidx[s+k-1]
			old = cnt[id]
			if old > 0 {
				freq[old]--
			}
			old++
			cnt[id] = old
			freq[old]++
			if old > maxFreq {
				maxFreq = old
			}
			B[s] = maxFreq
		}

		P := make([]int, m+1)
		N := make([]int, m+1)
		stack := make([]int, m)
		top := 0

		for i := 1; i <= m; i++ {
			for top > 0 && B[stack[top-1]] <= B[i] {
				top--
			}
			if top > 0 {
				P[i] = stack[top-1]
			}
			stack[top] = i
			top++
		}

		top = 0
		for i := m; i >= 1; i-- {
			for top > 0 && B[stack[top-1]] < B[i] {
				top--
			}
			if top > 0 {
				N[i] = stack[top-1]
			} else {
				N[i] = m + 1
			}
			stack[top] = i
			top++
		}

		headQ := make([]int, m+1)
		for i := range headQ {
			headQ[i] = -1
		}
		qL := make([]int, q)
		nextQ := make([]int, q)
		ans := make([]int64, q)

		for i := 0; i < q; i++ {
			l := nextInt(data, &p)
			r := nextInt(data, &p)
			rr := r - k + 1
			qL[i] = l
			nextQ[i] = headQ[rr]
			headQ[rr] = i
		}

		headM := make([]int, m+1)
		for i := range headM {
			headM[i] = -1
		}
		nextM := make([]int, m+1)
		for i := 1; i <= m; i++ {
			if N[i] <= m {
				nextM[i] = headM[N[i]]
				headM[N[i]] = i
			}
		}

		nbit := m + 1
		size64 := nbit + 1
		bits := make([]int64, size64*6)
		u1a := bits[0:size64]
		u1b := bits[size64 : 2*size64]
		u2a := bits[2*size64 : 3*size64]
		u2b := bits[3*size64 : 4*size64]
		sa := bits[4*size64 : 5*size64]
		sb := bits[5*size64 : 6*size64]

		for R := 1; R <= m; R++ {
			for i := headM[R]; i != -1; i = nextM[i] {
				c := int64(B[i])
				addLeft(u1a, u1b, nbit, i, P[i], -c)
				addLeft(u2a, u2b, nbit, i, P[i], -c*int64(i))
				addLeft(sa, sb, nbit, i, P[i], c*int64(N[i]-i))
			}

			i := R
			c := int64(B[i])
			addLeft(u1a, u1b, nbit, i, P[i], c)
			addLeft(u2a, u2b, nbit, i, P[i], c*int64(i))

			for qi := headQ[R]; qi != -1; qi = nextQ[qi] {
				l := qL[qi]
				x := l
				var a1, b1, a2, b2, a3, b3 int64
				for x > 0 {
					a1 += u1a[x]
					b1 += u1b[x]
					a2 += u2a[x]
					b2 += u2b[x]
					a3 += sa[x]
					b3 += sb[x]
					x -= x & -x
				}
				u1 := a1*int64(l) + b1
				u2 := a2*int64(l) + b2
				sv := a3*int64(l) + b3
				sumMax := int64(R+1)*u1 - u2 + sv
				length := int64(R - l + 1)
				ans[qi] = int64(k)*length*(length+1)/2 - sumMax
			}
		}

		for i := 0; i < q; i++ {
			out = strconv.AppendInt(out, ans[i], 10)
			out = append(out, '\n')
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	w.Write(out)
	w.Flush()
}
```