package main

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

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

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}

	for tc := 0; tc < t; tc++ {
		var n, m int
		fmt.Fscan(in, &n, &m)

		type interval struct{ l, r int }
		ivs := make([]interval, m)
		for i := 0; i < m; i++ {
			fmt.Fscan(in, &ivs[i].l, &ivs[i].r)
		}

		type block struct {
			z, w, cost []int
		}
		var blocks []block

		curr := 1
		for _, iv := range ivs {
			for curr < iv.l {
				blocks = append(blocks, block{
					z:    []int{1, 0},
					w:    []int{0, 1},
					cost: []int{0, 0},
				})
				curr++
			}
			length := iv.r - iv.l + 1
			var z, w, cost []int
			for k := 1; k < length; k++ {
				z = append(z, k)
				w = append(w, length - k)
				cost = append(cost, k*(length-k))
			}
			blocks = append(blocks, block{
				z:    z,
				w:    w,
				cost: cost,
			})
			curr = iv.r + 1
		}
		for curr <= n {
			blocks = append(blocks, block{
				z:    []int{1, 0},
				w:    []int{0, 1},
				cost: []int{0, 0},
			})
			curr++
		}

		const INF = 1000000000 
		dp := make([]int, n+1)
		for i := range dp {
			dp[i] = INF
		}
		dp[0] = 0

		for _, b := range blocks {
			nextDP := make([]int, n+1)
			for i := range nextDP {
				nextDP[i] = INF
			}
			for i := range b.z {
				zz := b.z[i]
				ww := b.w[i]
				cc := b.cost[i]
				for Z := 0; Z <= n-zz; Z++ {
					if dp[Z] != INF {
						cand := dp[Z] + ww*Z + cc
						if cand < nextDP[Z+zz] {
							nextDP[Z+zz] = cand
						}
					}
				}
			}
			dp = nextDP
		}

		minCost := INF
		for _, val := range dp {
			if val < minCost {
				minCost = val
			}
		}

		if minCost == INF {
			fmt.Fprintln(out, -1)
		} else {
			fmt.Fprintln(out, n*(n-1)/2-minCost)
		}
	}
}