WEIS

La empresa Weis desarrolla software pare calcular rutas de menor duración de un punto a otro en la ciudad. Para lograrlo, Weis tiene en cuenta el tráfico, la distancia y la velocidad permitida en las diferentes calles. Weis representa el tiempo que toma ir de un lugar a otro como una matriz cuadrada, es decir, una matriz que tiene el mismo número de filas que de columnas. En esa matriz, la posición (i,j) representa el tiempo que se demora para ir de un punto i a punto j. Es claro que posición (i,i), para cualquier valor de i, debe ser cero, pues para ir de un punto a sí mismo se toma cero minutos. Desafortunadamente, Weis está teniendo problemas con su software y algunas veces aparecen valores que no son cero en la posición (i,i) de la matriz. Ellos necesitan que tú les digas si hubo un problema en el cálculo de la matriz y aparecieron valores que no son cero en alguna posición (i,i) de la matriz o si todo está bien.

Input

La entrada consistirá en una serie de matrices. Para cada matriz, primero aparecerá la dimensión de la matriz. Después aparecerá en una línea separada cada una de las filas de la matriz. La entrada terminará cuando la línea tenga un 0.

Output

Por cada matriz, imprima true si la matriz tiene solamente valores 0 en la posición (i,i) para todo i, o imprima false si esta propiedad no se cumple.

Example

Input:
2
0
1
3
0
3
0
1
2
1
0
2
4
2
0
3
1
2
3
1
0
2
4
2
0
2
0
1
1
1
0

Output:
true
true
false
false