package main

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

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

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

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

type Interval struct {
	l, r int
}

type Comp struct {
	L, R int
	a, b int
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := in.NextInt()
	const INF int64 = 1 << 60

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

		intervals := make([]Interval, m)
		diff := make([]int, n+2)

		for i := 0; i < m; i++ {
			l := in.NextInt()
			r := in.NextInt()
			intervals[i] = Interval{l, r}
			diff[l]++
			diff[r]--
		}

		covered := make([]bool, n)
		cur := 0
		for i := 1; i <= n-1; i++ {
			cur += diff[i]
			covered[i] = cur > 0
		}

		compID := make([]int, n+1)
		comps := make([]Comp, 0)
		L := 1
		for i := 1; i <= n-1; i++ {
			if !covered[i] {
				id := len(comps)
				comps = append(comps, Comp{L: L, R: i, a: 0, b: i - L + 1})
				for p := L; p <= i; p++ {
					compID[p] = id
				}
				L = i + 1
			}
		}
		id := len(comps)
		comps = append(comps, Comp{L: L, R: n, a: 0, b: n - L + 1})
		for p := L; p <= n; p++ {
			compID[p] = id
		}

		ok := true
		for _, it := range intervals {
			id := compID[it.l]
			c := &comps[id]
			low := it.l - c.L + 1
			high := it.r - c.L
			if low > c.a {
				c.a = low
			}
			if high < c.b {
				c.b = high
			}
		}

		for i := range comps {
			if comps[i].a > comps[i].b {
				ok = false
				break
			}
		}

		if !ok {
			fmt.Fprintln(out, -1)
			continue
		}

		prev := make([]int64, n+1)
		for i := range prev {
			prev[i] = INF
		}
		prev[0] = 0
		minOnes, maxOnes := 0, 0

		for _, c := range comps {
			length := c.R - c.L + 1
			next := make([]int64, n+1)
			for i := range next {
				next[i] = INF
			}
			newMin := minOnes + c.a
			newMax := maxOnes + c.b

			for o := minOnes; o <= maxOnes; o++ {
				if prev[o] == INF {
					continue
				}
				base := prev[o]
				for x := c.a; x <= c.b; x++ {
					s := o + x
					cost := base + int64(o+x)*int64(length-x)
					if cost < next[s] {
						next[s] = cost
					}
				}
			}

			prev = next
			minOnes, maxOnes = newMin, newMax
		}

		minBad := INF
		for i := minOnes; i <= maxOnes; i++ {
			if prev[i] < minBad {
				minBad = prev[i]
			}
		}

		if minBad == INF {
			fmt.Fprintln(out, -1)
			continue
		}

		ans := int64(n) * int64(n-1) / 2
		ans -= minBad
		fmt.Fprintln(out, ans)
	}
}