```go
package main

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

var (
	reader *bufio.Reader
	writer *bufio.Writer
)

func init() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
}

func scan(a ...interface{}) { fmt.Fscan(reader, a...) }
func print(a ...interface{}) { fmt.Fprint(writer, a...) }
func println(a ...interface{}) { fmt.Fprintln(writer, a...) }

const INF = 1000000000

// Segment Tree
type SegTree struct {
	tree []int
	sz   int
}

// Global storage to avoid reallocation overhead
var trees [12]SegTree
var treeBuf []int

// Initialize trees for k+1 states and size n
func initTrees(k, n int) {
	sz := 1
	for sz <= n {
		sz *= 2
	}
	
	needed := (k + 1) * 2 * sz
	if len(treeBuf) < needed {
		treeBuf = make([]int, needed)
	}
	
	offset := 0
	for i := 0; i <= k; i++ {
		trees[i].sz = sz
		trees[i].tree = treeBuf[offset : offset+2*sz]
		// Reset valid range to -INF
		for j := 0; j < 2*sz; j++ {
			trees[i].tree[j] = -INF
		}
		offset += 2 * sz
	}
}

func (st *SegTree) Update(p, v int) {
	p += st.sz
	if v > st.tree[p] {
		st.tree[p] = v
		for p > 1 {
			p /= 2
			v1 := st.tree[2*p]
			v2 := st.tree[2*p+1]
			if v1 > v2 {
				st.tree[p] = v1
			} else {
				st.tree[p] = v2
			}
		}
	}
}

func (st *SegTree) Query(l, r int) int {
	if l > r {
		return -INF
	}
	l += st.sz
	r += st.sz
	res := -INF
	for l <= r {
		if l%2 == 1 {
			if st.tree[l] > res {
				res = st.tree[l]
			}
			l++
		}
		if r%2 == 0 {
			if st.tree[r] > res {
				res = st.tree[r]
			}
			r--
		}
		l /= 2
		r /= 2
	}
	return res
}

type Event struct {
	pos  int
	kind int // 1 for start, -1 for end
	id   int
}

func solve() {
	var n, m, k int
	scan(&n, &m, &k)

	lArr := make([]int, m+1)
	events := make([]Event, 0, 2*m)

	for i := 1; i <= m; i++ {
		var l, r int
		scan(&l, &r)
		lArr[i] = l
		events = append(events, Event{pos: l, kind: 1, id: i})
		events = append(events, Event{pos: r + 1, kind: -1, id: i})
	}

	// Sort events: by pos, then process removes (-1) before adds (1) to handle intervals ending at x-1 correctly?
    // Wait, standard sweep line:
    // At x, intervals ending at x-1 are removed. (Event pos x).
    // Intervals starting at x are added. (Event pos x).
    // So both happen at x.
    // We want active set valid for x.
    // Remove (kind -1) first, then Add (kind 1).
	sort.Slice(events, func(i, j int) bool {
		if events[i].pos != events[j].pos {
			return events[i].pos < events[j].pos
		}
		return events[i].kind < events[j].kind
	})

	initTrees(k, n)
	trees[0].Update(0, 0)

	active := make([]int, 0, m)
	posInActive := make([]int, m+1)
	for i := range posInActive {
		posInActive[i] = -1
	}
    activeCount := 0

	evtIdx := 0
    newDP := make([]int, k+1)

	for x := 1; x <= n; x++ {
		for evtIdx < len(events) && events[evtIdx].pos == x {
			e := events[evtIdx]
			if e.kind == 1 {
				activeCount++
				active = append(active, e.id)
				posInActive[e.id] = len(active) - 1
			} else {
				activeCount--
				id := e.id
				idx := posInActive[id]
                if idx != -1 {
                    last := active[len(active)-1]
                    active[idx] = last
                    posInActive[last] = idx
                    active = active[:len(active)-1]
                    posInActive[id] = -1
                }
			}
			evtIdx++
		}

		if activeCount <= k {
			currentIntervals := make([]int, len(active))
			copy(currentIntervals, active)
			sort.Slice(currentIntervals, func(i, j int) bool {
				return lArr[currentIntervals[i]] < lArr[currentIntervals[j]]
			})

            for i := 0; i <= k; i++ { newDP[i] = -INF }
            
            mCnt := len(currentIntervals)
            prevL := 0
            
            for idx, id := range currentIntervals {
                l := lArr[id]
                cost := mCnt - idx
                if l > prevL {
                     // Query range [prevL, l-1] with cost
                     for j := cost; j <= k; j++ {
                         v := trees[j-cost].Query(prevL, l-1)
                         if v != -INF && v+1 > newDP[j] {
                             newDP[j] = v + 1
                         }
                     }
                }
                prevL = l
            }
            if x > prevL {
                for j := 0; j <= k; j++ {
                    v := trees[j].Query(prevL, x-1)
                    if v != -INF && v+1 > newDP[j] {
                        newDP[j] = v + 1
                    }
                }
            }
            
            for j := 0; j <= k; j++ {
                if newDP[j] > -INF {
                    trees[j].Update(x, newDP[j])
                }
            }
		}
	}

	ans := 0
	for j := 0; j <= k; j++ {
		v := trees[j].Query(1, n)
		if v > ans {
			ans = v
		}
	}
	println(ans)
}

func main() {
    defer writer.Flush()
	var t int
	scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}
```