Informática - Nível Avançado - Semana 37

El primo

Enzo está jogando o seu jogo favorito "Brawl Stars" com o seu herói favorito -- El primo. Na nova atualização do jogo, várias mecânicas foram adicionadas, sendo uma delas a de cozinhar o seu jantar. Para isso, ele tem que pegar um retângulo de altura $h$ e comprimento $w$, e então fazer um corte horizontal ou vertical de modo que os dois retângulos que sobrarem tenham lados inteiros. Depois disso, ele vai pegar um dos retângulos, colocar numa caixa, e cortar o outro retângulo, e assim vai.

Mais formalmente, um retângulo de tamanho $h \times W$ pode ser cortado em duas partes de tamanhos $x \times w$ e $(h-x) \times w$, onde $x$ é um inteiro entre $1$ e $h-1$, ou em duas partes de tamanho $h \times y$ e $h \times (w-y)$, onde $y$ é um inteiro entre $1$ e $w-1$.

Então, El primo vai repetir essa operação $n-1$ vezes, e colocar o retângulo que sobrou na caixa também. Então a caixa vai conter $n$ retângulos, onde $n-1$ deles foram colocados pelo resultado dos cortes, e o $n$-ésimo retângulo sendo o que o El primo deixou depois de $n-1$ operações.

Infelizmente, Enzo esqueceu dos valores de $h$ e $w$, mas ele ainda tem $n$ retângulos misturados em uma ordem aleatória. Veja que El primo não girou os retângulos, só embaralhou eles. Agora Enzo quer saber todos os pares $(h, w)$ no qual o conjunto de retângulos na caixa podem gerar, e você tem que ajudar ele!

É garantido que existe pelo menos um par $(h, w)$ no qual esse conjunto de retângulos pode ser obtido.

Entrada

Cada caso teste consiste de multiplos casos. A primeira linha contém um inteiro $t (1 \le t \le 10^4)$, o número de casos testes. A descrição segue da seguinte maneira:

A primeira linha contém um único inteiro $n (1 \le n \le 2\times 10^5)$, o número de retângulos obtidos.

A $i-$ésima linha das próximas $n$ linhas conteém dois inteiros $a_i, b_i (1 \le a_i, b_i \le 10^6)$ - A altura e o comprimento do $i$-ésimo retângulo.

É garantido que a soma de todos os $n$ em todos os casos testes não passa de $2 \times 10^5$.

Saída

Para cada caso teste, na primeira linha, imprima um inteiro $m$, a quantidade de pares $(h, w)$, denotando os lados do retângulos que podem ser gerados. Dois retângulos são diferentes se eles tem alturas ou comprimentos diferentes.

Nas próximas $m$ linhas, imprima dois inteiros $h_i, w_i$, a altura e o comprimento dos retângulos que podem ser obtidos. Você pode imprimir eles em qualquer ordem.

4
3
1 2
3 5
1 3
3
1 1
1 1
1 1
1
10 10
4
3 2
5 5
2 2
8 7

1
4 5
2
1 3
3 1
1
10 10
1
13 7

Para submeter sua solução use esse link.