URI Online Judge | 1791

Descobrindo uma Matriz

Por Thalyson Nepomuceno, UECE BR Brazil

Timelimit: 1

Uma matriz é uma Matriz de Potências se atende 3 pré-requisitos:


1. É uma matriz quadrada.
2. A primeira coluna é formada apenas por 1's.
3. Para todo elemento (i, j) com j > 1, (i, j) = (i, 2)j-1 e (i, j) é diferente de zero.

Por exemplo:

Sua tarefa é descobrir se uma matriz quadrada pode ser transformada em uma Matriz de Potências utilizando dois tipos de operações:

1. Troca(x, y): Inverte as posições de todos os elementos das colunas x e y da matriz.
2. Transposta(): A matriz é transposta.

Por exemplo:

Logo P pode ser transformada em uma Matriz de Potência.

Entrada

A entrada consiste de múltiplas linhas. A primeira linha contém um inteiro C que indica o número de casos de teste. Em seguida, em cada caso de teste a primeira linha contém um inteiro N (1 < N < 8) que indica o número de linhas e colunas da matriz, em seguida N linhas, cada uma com N inteiros d (􀀀-50000 < d < 50000) representando os elementos da matriz .

Saída

Imprima em uma única linha para cada caso de teste a "Potencia" (sem aspas) caso a matriz possa ser transformada, ou "Nao Potencia" (sem aspas) caso contrário.

Exemplo de Entrada Exemplo de Saída

3
3
16 1 4
1 1 1
9 1 3
3
25 36 9
1 1 1
5 6 3
3
9 35 25
3 6 5
1 1 1

Potencia
Potencia
Nao Potencia