A sua equipe já está fazendo planos para a visita ao Egito. Um dos locais que querem conhecer é o famoso mercado do Cairo. Para economizar tempo, vocês decidiram que vão entrar pela porta no canto sudoeste do mercado e sair pela porta no canto nordeste. Além disso, vocês vão caminhar sempre em direção à saída, ou seja, só vão se deslocar para o norte ou para o leste.
Os vendedores egípcios tem uma regra peculiar. Se você comprar algo de um deles, só poderá comprar novamente de um outro vendedor que seja mais velho. A punição por desrespeitar essa regra é perder uma mão. É claro que isso pode prejudicar sua equipe na final do ICPC. Por este motivo, você acha melhor seguir as tradições locais. Como não é nada elegante dar o mesmo tipo de lembrança para todos seus amigos, você decidiu que, além de seguir as regras do mercado, vai comprar no máximo uma lembrança de cada vendedor. Isto lhe ajudará a ter uma boa variedade de presentes.
O mercado é bem organizado. Os vãos onde as barracas podem ser colocadas possuem a mesma altura e largura. Cada vão é identificado por uma coordenada (x,y) que indica a coluna e linha do mercado que ele se encontra. De uma vista aérea é possível perceber que todos os vãos estão organizados como um quadriculado. As barracas do mercado foram montadas apenas em vãos válidos (e respeitam rigorosamente as medidas do vão). Estando em uma barraca é possível ir para as barracas que ficam estritamente ao norte, ao leste e a nordeste.
Sabendo a idade dos vendedores e a posição da barraca onde cada um trabalha, determine o número máximo de itens que você pode comprar.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira linha de cada instância contém um inteiro N (1 ≤ N ≤ 100 000), indicando o número de vendedores no mercado. Cada uma das próximas N linhas contém dois inteiros cada, x_i e y_i (1 ≤ x_i,y_i ≤ 1 000), indicando as coordenadas da barraca em que o i-ésimo vendedor trabalha. Os vendedores estão listados em ordem de idade, do mais novo para o mais velho. Dois ou mais vendedores podem dividir uma mesma barraca. Nesse caso você pode negociar (ou deixar de negociar) com eles em qualquer ordem.
Ir para o norte significa aumentar o valor de y e ir para o leste significa aumentar o valor de x. Todas as barracas se encontram dentro do mercado.

Saída

Para cada instância imprima uma linha contendo um único inteiro, o número máximo de itens que você pode comprar.

Exemplo

Entrada:
5
1
1 1
2
1 1
1 2
2
2 1
1 1
3
1 1
1 2
2 1
4
1 1
1 2
2 1
2 2

Saída:
1
2
1
2
3