package main

import (
	"bufio"
	"fmt"
	"os"
)

func nextInt(in *bufio.Reader) int {
	n := 0
	c, err := in.ReadByte()
	if err != nil {
		return 0
	}
	for c <= 32 {
		c, err = in.ReadByte()
		if err != nil {
			return 0
		}
	}
	sign := 1
	if c == '-' {
		sign = -1
		c, _ = in.ReadByte()
	}
	for c > 32 {
		n = n*10 + int(c-'0')
		c, err = in.ReadByte()
		if err != nil {
			break
		}
	}
	return n * sign
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	t := nextInt(in)

	for tc := 0; tc < t; tc++ {
		n := nextInt(in)
		k := nextInt(in)
		q := nextInt(in)

		a := make([]int, n)
		for i := 0; i < n; i++ {
			a[i] = nextInt(in)
		}

		A := make([]int, n)
		for i := 0; i < n; i++ {
			A[i] = a[i] - i + n
		}

		freq := make([]int, 2*n+5)
		countFreq := make([]int, k+1)
		maxF := 0

		add := func(x int) {
			f := freq[x]
			if f > 0 {
				countFreq[f]--
			}
			freq[x]++
			f++
			countFreq[f]++
			if f > maxF {
				maxF = f
			}
		}

		remove := func(x int) {
			f := freq[x]
			countFreq[f]--
			freq[x]--
			f--
			if f > 0 {
				countFreq[f]++
			}
			for maxF > 0 && countFreq[maxF] == 0 {
				maxF--
			}
		}

		c := make([]int, n-k+1)
		for i := 0; i < k; i++ {
			add(A[i])
		}
		c[0] = k - maxF
		for i := 1; i <= n-k; i++ {
			remove(A[i-1])
			add(A[i+k-1])
			c[i] = k - maxF
		}

		type Query struct {
			m  int
			id int
		}
		queries := make([][]Query, n-k+1)
		for i := 0; i < q; i++ {
			l := nextInt(in) - 1
			r := nextInt(in) - 1
			m := r - k + 1
			queries[l] = append(queries[l], Query{m, i})
		}

		N := n - k + 1
		bit1 := make([]int64, N+2)
		bit2 := make([]int64, N+2)

		addBIT := func(i int, v int64) {
			for x := i; x <= N; x += x & -x {
				bit1[x] += v
				bit2[x] += v * int64(i-1)
			}
		}

		rangeAdd := func(l, r int, v int64) {
			addBIT(l, v)
			addBIT(r+1, -v)
		}

		queryBIT := func(i int) int64 {
			var s1, s2 int64
			for x := i; x > 0; x -= x & -x {
				s1 += bit1[x]
				s2 += bit2[x]
			}
			return s1*int64(i) - s2
		}

		rangeQuery := func(l, r int) int64 {
			return queryBIT(r) - queryBIT(l-1)
		}

		type Element struct {
			val int64
			idx int
			cnt int
		}
		stack := make([]Element, 0)
		ans := make([]int64, q)

		for l := N - 1; l >= 0; l-- {
			curr := Element{val: int64(c[l]), idx: l + 1, cnt: 1}

			for len(stack) > 0 && stack[len(stack)-1].val >= curr.val {
				top := stack[len(stack)-1]
				stack = stack[:len(stack)-1]

				diff := curr.val - top.val
				rangeAdd(top.idx, top.idx+top.cnt-1, diff)

				curr.cnt += top.cnt
			}

			rangeAdd(l+1, l+1, curr.val)
			stack = append(stack, curr)

			for _, query := range queries[l] {
				ans[query.id] = rangeQuery(l+1, query.m+1)
			}
		}

		for i := 0; i < q; i++ {
			fmt.Fprintln(out, ans[i])
		}
	}
}