1697 - Jaida e o Jogo Multiplicativo

ID: 1697
IdBecrowd: 1697
Tags: ad-hoc, matematica
Nível: 9
Tempo Limite: 2 segundos
Memória: 200 MB
Categoria: Matemática
Autor: Bugs, Lucas y Coyote, Universidad Católica San Pablo

Descrição

Jaida adora inteiros positivos. Agora ela está jogando um jogo chamado “jogo de multiplicar”.

“Jogo de multiplicar” é um jogo educativo no qual você tem uma lista de N números. Você pode escolher qualquer par desses números e adicionar o resultado da multiplicação deles na lista. Você pode fazer essa operação quantas vezes quiser.

Jaida quer que a lista contenha todos os números de 1 a X (mas pode haver repetições ou números maiores). Ajude a pequena Jaida dizendo-a qual é o maior valor de X que ela pode obter.

Entrada

A primeira linha da entrada contém um inteiro T que representa o número de casos de teste. Cada caso de teste é descrito em 2 linhas:

                A primeira linha contém o número

N (0 < N <= 10 6 ) como explicado acima. A segunda linha contém N inteiros positivos a i , que são os números iniciais da lista de Jaida (0 < a i <= 10 9 ).

Saída

Para cada caso de teste imprima uma linha contendo o maior valor de X que Jaida pode obter. Se for impossível, imprima 0 .

Exemplos

Exemplo de Entrada

3

                                6

                                1 2 3 4 5 12

                                3

                                2 3 4

                                3

                                1 2 3

Exemplo de Saída