package main

import (
	"bufio"
	"bytes"
	"os"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := os.ReadFile("/dev/stdin")
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c >= '0' && c <= '9' || c == '-' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return val * sign
}

func main() {
	in := NewFastScanner()
	t := in.NextInt()
	var out bytes.Buffer

	for ; t > 0; t-- {
		n := in.NextInt()
		k := in.NextInt()
		q := in.NextInt()

		shift := n + 2
		size := 2*n + 10
		vals := make([]int, n+1)
		for i := 1; i <= n; i++ {
			a := in.NextInt()
			vals[i] = a - i + shift
		}

		ans := make([]int, n-k+2)
		freq := make([]int, size)
		bucket := make([]int, k+2)
		curMax := 0

		add := func(v int) {
			old := freq[v]
			if old > 0 {
				bucket[old]--
			}
			old++
			freq[v] = old
			bucket[old]++
			if old > curMax {
				curMax = old
			}
		}

		remove := func(v int) {
			old := freq[v]
			bucket[old]--
			old--
			freq[v] = old
			if old > 0 {
				bucket[old]++
			}
			for curMax > 0 && bucket[curMax] == 0 {
				curMax--
			}
		}

		for i := 1; i <= k; i++ {
			add(vals[i])
		}
		ans[1] = k - curMax
		for l := 2; l <= n-k+1; l++ {
			remove(vals[l-1])
			add(vals[l+k-1])
			ans[l] = k - curMax
		}

		for i := 0; i < q; i++ {
			l := in.NextInt()
			_ = in.NextInt()
			out.WriteString(intToString(ans[l]))
			out.WriteByte('\n')
		}
	}

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

func intToString(x int) string {
	if x == 0 {
		return "0"
	}
	var buf [20]byte
	i := len(buf)
	for x > 0 {
		i--
		buf[i] = byte('0' + x%10)
		x /= 10
	}
	return string(buf[i:])
}