#!/usr/bin/python
# -*- coding: utf-8 -*-
# this implementation of the Strassen algorithm is from
# https://g...content-available-to-author-only...b.com/MartinThoma/matrix-multiplication
from math import ceil, log
def ikjMatrixProduct(A, B):
n = len(A)
C = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
for k in xrange(n):
for j in xrange(n):
C[i][j] += A[i][k] * B[k][j]
return C
def add(A, B):
n = len(A)
C = [[0 for j in xrange(0, n)] for i in xrange(0, n)]
for i in xrange(0, n):
for j in xrange(0, n):
C[i][j] = A[i][j] + B[i][j]
return C
def subtract(A, B):
n = len(A)
C = [[0 for j in xrange(0, n)] for i in xrange(0, n)]
for i in xrange(0, n):
for j in xrange(0, n):
C[i][j] = A[i][j] - B[i][j]
return C
def strassenR(A, B):
""" Implementation of the strassen algorithm, similar to
http://e...content-available-to-author-only...a.org/w/index.php?title=Strassen_algorithm&oldid=498910018#Source_code_of_the_Strassen_algorithm_in_C_language
"""
n = len(A)
if n <= LEAF_SIZE:
return ikjMatrixProduct(A, B)
else:
# initializing the new sub-matrices
newSize = n/2
a11 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
a12 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
a21 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
a22 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
b11 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
b12 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
b21 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
b22 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
aResult = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
bResult = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
# dividing the matrices in 4 sub-matrices:
for i in xrange(0, newSize):
for j in xrange(0, newSize):
a11[i][j] = A[i][j] # top left
a12[i][j] = A[i][j + newSize] # top right
a21[i][j] = A[i + newSize][j] # bottom left
a22[i][j] = A[i + newSize][j + newSize] # bottom right
b11[i][j] = B[i][j] # top left
b12[i][j] = B[i][j + newSize] # top right
b21[i][j] = B[i + newSize][j] # bottom left
b22[i][j] = B[i + newSize][j + newSize] # bottom right
# Calculating p1 to p7:
aResult = add(a11, a22)
bResult = add(b11, b22)
p1 = strassenR(aResult, bResult) # p1 = (a11+a22) * (b11+b22)
aResult = add(a21, a22) # a21 + a22
p2 = strassenR(aResult, b11) # p2 = (a21+a22) * (b11)
bResult = subtract(b12, b22) # b12 - b22
p3 = strassenR(a11, bResult) # p3 = (a11) * (b12 - b22)
bResult = subtract(b21, b11) # b21 - b11
p4 =strassenR(a22, bResult) # p4 = (a22) * (b21 - b11)
aResult = add(a11, a12) # a11 + a12
p5 = strassenR(aResult, b22) # p5 = (a11+a12) * (b22)
aResult = subtract(a21, a11) # a21 - a11
bResult = add(b11, b12) # b11 + b12
p6 = strassenR(aResult, bResult) # p6 = (a21-a11) * (b11+b12)
aResult = subtract(a12, a22) # a12 - a22
bResult = add(b21, b22) # b21 + b22
p7 = strassenR(aResult, bResult) # p7 = (a12-a22) * (b21+b22)
# calculating c21, c21, c11 e c22:
c12 = add(p3, p5) # c12 = p3 + p5
c21 = add(p2, p4) # c21 = p2 + p4
aResult = add(p1, p4) # p1 + p4
bResult = add(aResult, p7) # p1 + p4 + p7
c11 = subtract(bResult, p5) # c11 = p1 + p4 - p5 + p7
aResult = add(p1, p3) # p1 + p3
bResult = add(aResult, p6) # p1 + p3 + p6
c22 = subtract(bResult, p2) # c22 = p1 + p3 - p2 + p6
# Grouping the results obtained in a single matrix:
C = [[0 for j in xrange(0, n)] for i in xrange(0, n)]
for i in xrange(0, newSize):
for j in xrange(0, newSize):
C[i][j] = c11[i][j]
C[i][j + newSize] = c12[i][j]
C[i + newSize][j] = c21[i][j]
C[i + newSize][j + newSize] = c22[i][j]
return C
def strassen(A, B):
assert type(A) == list and type(B) == list
assert len(A) == len(A[0]) == len(B) == len(B[0])
# Make the matrices bigger so that you can apply the strassen
# algorithm recursively without having to deal with odd
# matrix sizes
nextPowerOfTwo = lambda n: 2**int(ceil(log(n,2)))
n = len(A)
m = nextPowerOfTwo(n)
APrep = [[0 for i in xrange(m)] for j in xrange(m)]
BPrep = [[0 for i in xrange(m)] for j in xrange(m)]
for i in xrange(n):
for j in xrange(n):
APrep[i][j] = A[i][j]
BPrep[i][j] = B[i][j]
CPrep = strassenR(APrep, BPrep)
C = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
for j in xrange(n):
C[i][j] = CPrep[i][j]
return C
def printMatrix(matrix):
for line in matrix:
print "\t".join(map(str,line))
if __name__ == "__main__":
LEAF_SIZE = 128
N = int(raw_input())
A = [[0 for i in xrange(N)] for j in xrange(N)]
for i in range(N):
ins = raw_input()
ins = list(ins)
ins = map(int,ins)
A[i] = ins
C = strassen(A, A)
ans = 0
for i in xrange(0,N):
for j in xrange(0,N):
if C[i][j] != 0 and i != j and A[i][j] != 1:
ans += 1
print ans
IyEvdXNyL2Jpbi9weXRob24KIyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KCiMgdGhpcyBpbXBsZW1lbnRhdGlvbiBvZiB0aGUgU3RyYXNzZW4gYWxnb3JpdGhtIGlzIGZyb20KIyBodHRwczovL2cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmIuY29tL01hcnRpblRob21hL21hdHJpeC1tdWx0aXBsaWNhdGlvbgoKZnJvbSBtYXRoIGltcG9ydCBjZWlsLCBsb2cKCmRlZiBpa2pNYXRyaXhQcm9kdWN0KEEsIEIpOgogICAgbiA9IGxlbihBKQogICAgQyA9IFtbMCBmb3IgaSBpbiB4cmFuZ2UobildIGZvciBqIGluIHhyYW5nZShuKV0KICAgIGZvciBpIGluIHhyYW5nZShuKToKICAgICAgICBmb3IgayBpbiB4cmFuZ2Uobik6CiAgICAgICAgICAgIGZvciBqIGluIHhyYW5nZShuKToKICAgICAgICAgICAgICAgIENbaV1bal0gKz0gQVtpXVtrXSAqIEJba11bal0KICAgIHJldHVybiBDCgpkZWYgYWRkKEEsIEIpOgogICAgbiA9IGxlbihBKQogICAgQyA9IFtbMCBmb3IgaiBpbiB4cmFuZ2UoMCwgbildIGZvciBpIGluIHhyYW5nZSgwLCBuKV0KICAgIGZvciBpIGluIHhyYW5nZSgwLCBuKToKICAgICAgICBmb3IgaiBpbiB4cmFuZ2UoMCwgbik6CiAgICAgICAgICAgIENbaV1bal0gPSBBW2ldW2pdICsgQltpXVtqXQogICAgcmV0dXJuIEMKCmRlZiBzdWJ0cmFjdChBLCBCKToKICAgIG4gPSBsZW4oQSkKICAgIEMgPSBbWzAgZm9yIGogaW4geHJhbmdlKDAsIG4pXSBmb3IgaSBpbiB4cmFuZ2UoMCwgbildCiAgICBmb3IgaSBpbiB4cmFuZ2UoMCwgbik6CiAgICAgICAgZm9yIGogaW4geHJhbmdlKDAsIG4pOgogICAgICAgICAgICBDW2ldW2pdID0gQVtpXVtqXSAtIEJbaV1bal0KICAgIHJldHVybiBDCgpkZWYgc3RyYXNzZW5SKEEsIEIpOgogICAgIiIiIEltcGxlbWVudGF0aW9uIG9mIHRoZSBzdHJhc3NlbiBhbGdvcml0aG0sIHNpbWlsYXIgdG8gCiAgICAgICAgaHR0cDovL2UuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEub3JnL3cvaW5kZXgucGhwP3RpdGxlPVN0cmFzc2VuX2FsZ29yaXRobSZvbGRpZD00OTg5MTAwMTgjU291cmNlX2NvZGVfb2ZfdGhlX1N0cmFzc2VuX2FsZ29yaXRobV9pbl9DX2xhbmd1YWdlCiAgICAiIiIKICAgIG4gPSBsZW4oQSkKCiAgICBpZiBuIDw9IExFQUZfU0laRToKICAgICAgICByZXR1cm4gaWtqTWF0cml4UHJvZHVjdChBLCBCKQogICAgZWxzZToKICAgICAgICAjIGluaXRpYWxpemluZyB0aGUgbmV3IHN1Yi1tYXRyaWNlcwogICAgICAgIG5ld1NpemUgPSBuLzIKICAgICAgICBhMTEgPSBbWzAgZm9yIGogaW4geHJhbmdlKDAsIG5ld1NpemUpXSBmb3IgaSBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSldCiAgICAgICAgYTEyID0gW1swIGZvciBqIGluIHhyYW5nZSgwLCBuZXdTaXplKV0gZm9yIGkgaW4geHJhbmdlKDAsIG5ld1NpemUpXQogICAgICAgIGEyMSA9IFtbMCBmb3IgaiBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSldIGZvciBpIGluIHhyYW5nZSgwLCBuZXdTaXplKV0KICAgICAgICBhMjIgPSBbWzAgZm9yIGogaW4geHJhbmdlKDAsIG5ld1NpemUpXSBmb3IgaSBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSldCgogICAgICAgIGIxMSA9IFtbMCBmb3IgaiBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSldIGZvciBpIGluIHhyYW5nZSgwLCBuZXdTaXplKV0KICAgICAgICBiMTIgPSBbWzAgZm9yIGogaW4geHJhbmdlKDAsIG5ld1NpemUpXSBmb3IgaSBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSldCiAgICAgICAgYjIxID0gW1swIGZvciBqIGluIHhyYW5nZSgwLCBuZXdTaXplKV0gZm9yIGkgaW4geHJhbmdlKDAsIG5ld1NpemUpXQogICAgICAgIGIyMiA9IFtbMCBmb3IgaiBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSldIGZvciBpIGluIHhyYW5nZSgwLCBuZXdTaXplKV0KCiAgICAgICAgYVJlc3VsdCA9IFtbMCBmb3IgaiBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSldIGZvciBpIGluIHhyYW5nZSgwLCBuZXdTaXplKV0KICAgICAgICBiUmVzdWx0ID0gW1swIGZvciBqIGluIHhyYW5nZSgwLCBuZXdTaXplKV0gZm9yIGkgaW4geHJhbmdlKDAsIG5ld1NpemUpXQoKICAgICAgICAjIGRpdmlkaW5nIHRoZSBtYXRyaWNlcyBpbiA0IHN1Yi1tYXRyaWNlczoKICAgICAgICBmb3IgaSBpbiB4cmFuZ2UoMCwgbmV3U2l6ZSk6CiAgICAgICAgICAgIGZvciBqIGluIHhyYW5nZSgwLCBuZXdTaXplKToKICAgICAgICAgICAgICAgIGExMVtpXVtqXSA9IEFbaV1bal0gICAgICAgICAgICAjIHRvcCBsZWZ0CiAgICAgICAgICAgICAgICBhMTJbaV1bal0gPSBBW2ldW2ogKyBuZXdTaXplXSAgICAjIHRvcCByaWdodAogICAgICAgICAgICAgICAgYTIxW2ldW2pdID0gQVtpICsgbmV3U2l6ZV1bal0gICAgIyBib3R0b20gbGVmdAogICAgICAgICAgICAgICAgYTIyW2ldW2pdID0gQVtpICsgbmV3U2l6ZV1baiArIG5ld1NpemVdICMgYm90dG9tIHJpZ2h0CiAKICAgICAgICAgICAgICAgIGIxMVtpXVtqXSA9IEJbaV1bal0gICAgICAgICAgICAjIHRvcCBsZWZ0CiAgICAgICAgICAgICAgICBiMTJbaV1bal0gPSBCW2ldW2ogKyBuZXdTaXplXSAgICAjIHRvcCByaWdodAogICAgICAgICAgICAgICAgYjIxW2ldW2pdID0gQltpICsgbmV3U2l6ZV1bal0gICAgIyBib3R0b20gbGVmdAogICAgICAgICAgICAgICAgYjIyW2ldW2pdID0gQltpICsgbmV3U2l6ZV1baiArIG5ld1NpemVdICMgYm90dG9tIHJpZ2h0CgogICAgICAgICMgQ2FsY3VsYXRpbmcgcDEgdG8gcDc6CiAgICAgICAgYVJlc3VsdCA9IGFkZChhMTEsIGEyMikKICAgICAgICBiUmVzdWx0ID0gYWRkKGIxMSwgYjIyKQogICAgICAgIHAxID0gc3RyYXNzZW5SKGFSZXN1bHQsIGJSZXN1bHQpICMgcDEgPSAoYTExK2EyMikgKiAoYjExK2IyMikKIAogICAgICAgIGFSZXN1bHQgPSBhZGQoYTIxLCBhMjIpICAgICAgIyBhMjEgKyBhMjIKICAgICAgICBwMiA9IHN0cmFzc2VuUihhUmVzdWx0LCBiMTEpICAjIHAyID0gKGEyMSthMjIpICogKGIxMSkKIAogICAgICAgIGJSZXN1bHQgPSBzdWJ0cmFjdChiMTIsIGIyMikgIyBiMTIgLSBiMjIKICAgICAgICBwMyA9IHN0cmFzc2VuUihhMTEsIGJSZXN1bHQpICAjIHAzID0gKGExMSkgKiAoYjEyIC0gYjIyKQogCiAgICAgICAgYlJlc3VsdCA9IHN1YnRyYWN0KGIyMSwgYjExKSAjIGIyMSAtIGIxMQogICAgICAgIHA0ID1zdHJhc3NlblIoYTIyLCBiUmVzdWx0KSAgICMgcDQgPSAoYTIyKSAqIChiMjEgLSBiMTEpCiAKICAgICAgICBhUmVzdWx0ID0gYWRkKGExMSwgYTEyKSAgICAgICMgYTExICsgYTEyCiAgICAgICAgcDUgPSBzdHJhc3NlblIoYVJlc3VsdCwgYjIyKSAgIyBwNSA9IChhMTErYTEyKSAqIChiMjIpICAgCiAKICAgICAgICBhUmVzdWx0ID0gc3VidHJhY3QoYTIxLCBhMTEpICMgYTIxIC0gYTExCiAgICAgICAgYlJlc3VsdCA9IGFkZChiMTEsIGIxMikgICAgICAjIGIxMSArIGIxMgogICAgICAgIHA2ID0gc3RyYXNzZW5SKGFSZXN1bHQsIGJSZXN1bHQpICMgcDYgPSAoYTIxLWExMSkgKiAoYjExK2IxMikKIAogICAgICAgIGFSZXN1bHQgPSBzdWJ0cmFjdChhMTIsIGEyMikgIyBhMTIgLSBhMjIKICAgICAgICBiUmVzdWx0ID0gYWRkKGIyMSwgYjIyKSAgICAgICMgYjIxICsgYjIyCiAgICAgICAgcDcgPSBzdHJhc3NlblIoYVJlc3VsdCwgYlJlc3VsdCkgIyBwNyA9IChhMTItYTIyKSAqIChiMjErYjIyKQoKICAgICAgICAjIGNhbGN1bGF0aW5nIGMyMSwgYzIxLCBjMTEgZSBjMjI6CiAgICAgICAgYzEyID0gYWRkKHAzLCBwNSkgIyBjMTIgPSBwMyArIHA1CiAgICAgICAgYzIxID0gYWRkKHAyLCBwNCkgICMgYzIxID0gcDIgKyBwNAogCiAgICAgICAgYVJlc3VsdCA9IGFkZChwMSwgcDQpICMgcDEgKyBwNAogICAgICAgIGJSZXN1bHQgPSBhZGQoYVJlc3VsdCwgcDcpICMgcDEgKyBwNCArIHA3CiAgICAgICAgYzExID0gc3VidHJhY3QoYlJlc3VsdCwgcDUpICMgYzExID0gcDEgKyBwNCAtIHA1ICsgcDcKIAogICAgICAgIGFSZXN1bHQgPSBhZGQocDEsIHAzKSAjIHAxICsgcDMKICAgICAgICBiUmVzdWx0ID0gYWRkKGFSZXN1bHQsIHA2KSAjIHAxICsgcDMgKyBwNgogICAgICAgIGMyMiA9IHN1YnRyYWN0KGJSZXN1bHQsIHAyKSAjIGMyMiA9IHAxICsgcDMgLSBwMiArIHA2CiAKICAgICAgICAjIEdyb3VwaW5nIHRoZSByZXN1bHRzIG9idGFpbmVkIGluIGEgc2luZ2xlIG1hdHJpeDoKICAgICAgICBDID0gW1swIGZvciBqIGluIHhyYW5nZSgwLCBuKV0gZm9yIGkgaW4geHJhbmdlKDAsIG4pXQogICAgICAgIGZvciBpIGluIHhyYW5nZSgwLCBuZXdTaXplKToKICAgICAgICAgICAgZm9yIGogaW4geHJhbmdlKDAsIG5ld1NpemUpOgogICAgICAgICAgICAgICAgQ1tpXVtqXSA9IGMxMVtpXVtqXQogICAgICAgICAgICAgICAgQ1tpXVtqICsgbmV3U2l6ZV0gPSBjMTJbaV1bal0KICAgICAgICAgICAgICAgIENbaSArIG5ld1NpemVdW2pdID0gYzIxW2ldW2pdCiAgICAgICAgICAgICAgICBDW2kgKyBuZXdTaXplXVtqICsgbmV3U2l6ZV0gPSBjMjJbaV1bal0KICAgICAgICByZXR1cm4gQwoKZGVmIHN0cmFzc2VuKEEsIEIpOgogICAgYXNzZXJ0IHR5cGUoQSkgPT0gbGlzdCBhbmQgdHlwZShCKSA9PSBsaXN0CiAgICBhc3NlcnQgbGVuKEEpID09IGxlbihBWzBdKSA9PSBsZW4oQikgPT0gbGVuKEJbMF0pCiAgICAjIE1ha2UgdGhlIG1hdHJpY2VzIGJpZ2dlciBzbyB0aGF0IHlvdSBjYW4gYXBwbHkgdGhlIHN0cmFzc2VuCiAgICAjIGFsZ29yaXRobSByZWN1cnNpdmVseSB3aXRob3V0IGhhdmluZyB0byBkZWFsIHdpdGggb2RkCiAgICAjIG1hdHJpeCBzaXplcwogICAgbmV4dFBvd2VyT2ZUd28gPSBsYW1iZGEgbjogMioqaW50KGNlaWwobG9nKG4sMikpKQogICAgbiA9IGxlbihBKQogICAgbSA9IG5leHRQb3dlck9mVHdvKG4pCiAgICBBUHJlcCA9IFtbMCBmb3IgaSBpbiB4cmFuZ2UobSldIGZvciBqIGluIHhyYW5nZShtKV0KICAgIEJQcmVwID0gW1swIGZvciBpIGluIHhyYW5nZShtKV0gZm9yIGogaW4geHJhbmdlKG0pXQogICAgZm9yIGkgaW4geHJhbmdlKG4pOgogICAgICAgIGZvciBqIGluIHhyYW5nZShuKToKICAgICAgICAgICAgQVByZXBbaV1bal0gPSBBW2ldW2pdCiAgICAgICAgICAgIEJQcmVwW2ldW2pdID0gQltpXVtqXQogICAgQ1ByZXAgPSBzdHJhc3NlblIoQVByZXAsIEJQcmVwKQogICAgQyA9IFtbMCBmb3IgaSBpbiB4cmFuZ2UobildIGZvciBqIGluIHhyYW5nZShuKV0KICAgIGZvciBpIGluIHhyYW5nZShuKToKICAgICAgICBmb3IgaiBpbiB4cmFuZ2Uobik6CiAgICAgICAgICAgIENbaV1bal0gPSBDUHJlcFtpXVtqXQogICAgcmV0dXJuIEMKCmRlZiBwcmludE1hdHJpeChtYXRyaXgpOgogICAgZm9yIGxpbmUgaW4gbWF0cml4OgogICAgICAgIHByaW50ICJcdCIuam9pbihtYXAoc3RyLGxpbmUpKQogICAgCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBMRUFGX1NJWkUgPSAxMjgKICAgIE4gPSBpbnQocmF3X2lucHV0KCkpCiAgICBBID0gW1swIGZvciBpIGluIHhyYW5nZShOKV0gZm9yIGogaW4geHJhbmdlKE4pXQogICAgZm9yIGkgaW4gcmFuZ2UoTik6CiAgICAgICAgaW5zID0gcmF3X2lucHV0KCkKICAgICAgICBpbnMgPSBsaXN0KGlucykKICAgICAgICBpbnMgPSBtYXAoaW50LGlucykKICAgICAgICBBW2ldID0gaW5zCiAgICBDID0gc3RyYXNzZW4oQSwgQSkKICAgIGFucyA9IDAKICAgIGZvciBpIGluIHhyYW5nZSgwLE4pOgogICAgICAgIGZvciBqIGluIHhyYW5nZSgwLE4pOgogICAgICAgICAgICBpZiBDW2ldW2pdICE9IDAgYW5kIGkgIT0gaiBhbmQgQVtpXVtqXSAhPSAxOgogICAgICAgICAgICAgICAgYW5zICs9IDEKICAgIHByaW50IGFucw==