Discovering an Matrix
By Thalyson Nepomuceno, UECE 
Brazil
By Thalyson Nepomuceno, UECE Brazil
A matrix is a Matriz de Potencia if it meets three requisites:
1. It is a square matrix.
2. The first column is formed only 1's.
3. For every element (i, j), with j > 1, (i, j) = (i, 2) j-1 and (i, j) is nonzero.
For example:
Your task is to find out if a square matrix can be transformed into a Matriz de Potencia using two types of operations:
1. Troca(x, y): Reverses the positions of all elements in columns x and y of the matrix.
2. Transposta(): The matrix is transposed.
For example:
Then P can be transformed into a Matriz de Potência.
The input consists of multiple lines. The first line contains an integer C that indicates the number of test cases. Then the first line in each test case contains an integer N (1 < N < 8) indicating the number of rows and columns of the matrix, then N lines, each with N integers d (-50000 < d < 50000) represents the matrix elements.
Each test case, print a single line with "Potencia" (without quotes) if the matrix can be transformed, or "Nao Potencia" (without quotes) if not.
| Input Sample | Output Sample |
|
3 |
Potencia |