Segmentos 3000

Lobo está muito triste, então, para se animar, ele foi jogar seu jogo favorito: Segmentos 3000. As regras desse jogo são as seguintes:

Uma array de segmentos $\{ [l_1, r_1], [l_2, r_2], \cdots, [l_k, r_k] \}$ é bonito se $k$ é par, e é possível dividir a array em $\frac{k}{2}$ pares de modo que

• Qualquer elemento da array está em exatamente um par.
• Segmentos no mesmo par se intersectam
• Segmentos em pares diferentes não se intersectam

Por exemplo, a array $\{ [2, 4], [9,12], [2, 4], [7, 7], [10,13], [6, 8] \}$ é bonita, pois, podemos dividir a array nos pares $\{ [2, 4], [2, 4] \} , \{ [9, 12], [10, 13] \} , \{ [7, 7] , [6, 8] \}$, que cumpre as condições acima.

O jogo funciona da seguinte maneira: Ele vai dar uma array de intervalos $[l_1, r_1], [l_2, r_2], \cdots , [l_n, r_n]$ e para ganhar, você tem que transformar essa array em bonita removendo elementos dela. Como o Lobo é muito competitivo, ele quer remover a menor quantidade de intervalos possível. Ajude ele nessa tarefa!

Input

A primeira linha contém um inteiro $t (1 \le t \le 1000)$ - A quantidade de rodadas do jogo

A primeira linha da rodada contém um inteiro $n (1 \le n \le 2000 )$ - O número de segmentos da array, e então, $n$ linhas, com a $i$-ésima linha contendo 2 números $l, r (1 \le l \le r \le 10^9)$, denotando o $i$-ésimo intervalo.

Além disso, é garantido que a soma dos $n$ de todas as rodadas não excede $2000$

Output

Para cada rodada do jogo, retorne um inteiro - O menor número de elementos que você tem que remover para que a array que sobre seja bonita

Exemplo

3
7
2 4
9 12
2 4
7 7
4 8
10 13
6 8
5
2 2
2 8
0 10
1 2
5 6
4
1 1
2 2
3 3
4 4

1
3
4

Para submeter sua solução use esse link