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