SPOJ Brasil

Para muita gente, o livro Introduction to Algorithms, de Cormen et al, é a “bíblia” da ciência da computação. Para alguns, literalmente.

A recém-fundada Igreja Cormeniana tem como um de seus preceitos principais que as mais de 1000 páginas do livro contêm, em um código secreto, a resposta para todas as questões fundamentais da humanidade. Questões como: De onde viemos? Por que estamos aqui? Para onde vamos? Onde vamos almoçar hoje?

A igreja precisa de sua ajuda para decifrar esse código e obter as respostas. Usando uma técnica secreta que só é conhecida pelo alto escalão da igreja, o livro foi segmentado em seções. Todas as letras de cada seção foram mapeadas em inteiros entre 1 e 26, e os demais caracteres (ex: pontuação) foram ignorados. Assim, uma seção pode ser entendida como uma sequência (potencialmente muito longa) de inteiros.

Cada seção pode ou não conter uma mensagem. O segredo para decifrar a mensagem contida em cada seção está nas subseqüências de uma seção cuja soma é exatamente 42. Essas subseqüências são conhecidas como “palavras de Adams”, em referência a um dos profetas da religião. Uma palavra de Adams pode ser especificada por um par de índices (a,b), tal que a < b e que a soma dos elementos da seção que estão no intervalo que começa no índice a e termina no índice b (inclusive) é 42.

Duas palavras de Adams possuem um overlap se há alguma sobreposição nos intervalos que as descrevem. Por exemplo, as palavras (1, 10) e (8, 14) possuem um overlap, pois os elementos nos índices 8, 9 e 10 pertencem à ambas.

Uma mensagem é uma sequência de palavras de Adams tal que não há nenhum overlap entre essas palavras. O tamanho de uma mensagem é definido pelo número de palavras de Adams que ela contém.

Dada uma seção, determine o tamanho da maior mensagem contida nela.

Entrada

A entrada começa com uma linha contendo um inteiro S, que representa o número total de seções que você deve analisar (0 < S <= 16).

Cada uma das S seções é então descrita em duas linhas. A primeira linha contém um inteiro N, o número de letras na seção (0 < N ≤ 1.048.576). A segunda linha contém N inteiros que representam as letras da seção, cada um dos quais está entre 1 e 26, inclusive.

Saída

Para cada seção na entrada, imprima uma linha na saída padrão contendo o tamanho da maior mensagem contida nela.

Exemplos

Entrada:
4
5
21 21 1 21 21
5
20 20 2 20 20
9
1 2 3 4 5 6 7 8 9
3
1 2 3

Saída:
2
1
1
0

No primeiro exemplo, há apenas duas palavras de Adams: (0, 1) e (3, 4) (consideramos o índice inicial como sendo zero). Como não há sobreposição entre elas, então o tamanho da maior mensagem é 2.

No segundo exemplo, há três palavras de Adams: (0, 2), (1, 3) e (2, 4). Porém, há sobreposição entre quaisquer duas delas. Portanto, a maior mensagem possui tamanho 1 --- note que, nesse caso, a maior mensagem não é única.

No terceiro exemplo, há apenas uma palavra de Adams: (2, 8). Logo, o tamanho da maior mensagem é 1.

No quarto exemplo, não há nenhuma palavra de Adams na seção e, portanto, a maior mensagem possui tamanho zero.