first.py

import math

f = open('input.in')
cases = int(f.readline())

for case in range(cases):
    m = [ ]
    lines = int(f.readline())

    # read and convert the matrix
    s = 0
    for i in range(lines):
        m.append([1 if j == '#' else 0 for j in f.readline()])
        s += sum(m[-1])

    # test if there might be a square matrix
    sum_on_a_line = int(math.sqrt(s))
    if not sum_on_a_line * sum_on_a_line == s:
        print "Case #%s: NO" % (case + 1)
        continue
    
    # get first row with a black cell
    while not filter(None, m[0]):
        m.pop(0)
    
    # get left right indices
    left = right = -1
    for i in range(len(m)):
        if m[0][i]:
            left = i
            break
    for i in reversed(range(len(m[0]))):
        if m[0][i]:
            right = i
            break
    
    # sum up the portion of the matrix where the square
    # should be
    new_sum = 0
    for line in range(sum_on_a_line):
        s = 0
        for i in range(left, right):
            s += line[i]
        if s == sum_on_a_line:
            new_sum += s
        else:
            break
    
    # test to see if the new_sum equals the old one
    if new_sum == s:
        print "Case #%s: YES" % (case + 1)
    else:
        print "Case #%s: NO" % (case + 1)