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.
| Entrada | Saída |
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 |