bee 1697 - Jaida e o Jogo Multiplicativo

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⁶) 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⁹).

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.

Exemplo de Entrada	Exemplo de Saída
3 6 1 2 3 4 5 12 3 2 3 4 3 1 2 3	6 0 4

Exemplo de Entrada

Exemplo de Saída

6
1 2 3 4 5 12
3
2 3 4
3
1 2 3

6
0
4