import random, math, time


class Grid(object):
    def __init__(self, n):
        self.n = n
        self.a = [[0]*n for _ in range(n)]
        self.filled = 0

    def __str__(self):
        return "\n".join("".join(str(c) for c in r) for r in self.a)

    def on(self, i, j):
        if not self.a[i][j]: self.filled += 1
        self.a[i][j] = 1

    def off(self, i, j):
        if self.a[i][j]: self.filled -= 1
        self.a[i][j] = 0

    def get_rand_ind(self):
        return (random.randint(0, self.n-1),random.randint(0, self.n-1))


    def check_squares(self, i, j):
        for d in range(-i, self.n-i):
            if d==0: continue
            for sgn in [-1, 1]:
                #if any(t<0 or t>=self.n for t in (i+d, j+sgn*d)): continue
                y1 = j+sgn*d
                if y1<0 or y1>=self.n: continue
                crns = [(i+d, j), (i+d, y1), (i, y1)]
                if all(self.a[x][y] for x,y in crns):
                    #print ("corners ", crns, " form square")
                    return True
        return False



    def sim_an(self, kMax=10**6):
        T = 1.0
        k = 0

        bestFilled = self.filled
        bestGrid = str(self)
        startT = time.time()
        while k<kMax:
            T = 1.0 - float(k)/kMax
            i,j = self.get_rand_ind()
            if self.a[i][j]:
                if random.random()<math.exp(-1.0/T):
                    self.off(i,j)
            else:
                if not self.check_squares(i,j):
                    self.on(i,j)
            if self.filled>bestFilled:
                bestFilled = self.filled
                bestGrid = str(self)
                print ("New Best: %d" %bestFilled)
                print ("T = %f" %T, "k = %d" %k)
                #print (bestGrid)
            k += 1

        print ("Simulated annealing over.")
        print ("Time: %f" %(time.time()-startT))
        print ("Best found: %d" %bestFilled)
        print (bestGrid)

    #for testing
    def print_possibs(self):
        ret = ""
        for i in range(self.n):
            for j in range(self.n):
                ret += "x" if self.check_squares(i,j) else "*"
            if i==self.n-1: break
            ret += "\n"
        print (ret)



testN = 100
g = Grid(testN)

g.sim_an(kMax = 10**9)







"""
T = 0.105702 k = 894298386
Simulated annealing over.
Time: 24389.976206
Best found: 3334

0110100011001011000000011000110100110000011101011010000100100010010011010000101110100000011110000000
1000100101001010100110100100100000010110010101001010000010100011101101100110101001001011110101000110
1100100000100111010101100101100001110000000000001100110111100101000110010011110011000001001001100000
0011101100100010000111001001000101001101100010111001000000110110001010000001001000110110010000100000
0101011010010011000010101011000010000110100010001011000110011100000111011000110101010011100000000001
0100010101101001000000001101001000110010110000110100000010010011100010001101011001000010000100011011
1001000011001000100101100001101010011110001011000001100101010001001010010000101100000010001001001101
0101010001011000011111000000101000100011000101110000001111100000001111100010010000001010100011001000
1011100011000010010010110001010000100101100101011101001000111101010001000100011110100011110100010001
1010000001100100100011011000001001001010110011000101001001101011010000001100100000100000101000110010
0111010111000000010001000010110001001011010001001001100000001110110001110011100010010000000000100001
0001011100001001001111000010011011000010010111100000001111010000010001000110001100000001000010110010
0010001001000001100100001000101000010111101001000000110100111000111000111000111000011000000110000000
1110101010000100000110110000000100011000000110010100010110000100001001101111010010001001010011001001
1001100000111100100010011011100010100010000010100011010011100000001000100101100001000100100110001001
1100110100000000100010010100010010100001100111000100110010000011010000010000010001001011000001000100
0001101010100100110000000110011000110000100000010001001101001110010000100000000011011110000100000100
0001000110111000000000110000001011001001101000000011101011110000000000100001010100010001000001110111
1011011000000101111000100100000000111101011110001010100100000100110000001100000100001000001100101001
0100101110001000000100000010000001101000000010011111000000000110100100000000000110100010011010111010
1001100001000000001000010111000101000110001000010000010101100001000001000110010100110101000010100010
1010100100101110001001100010100110000010101101010011010000010000010000001000010100101100111100000001
0110010011111001000000000100010000001010101001000010010000000011010001101100001010110000000001001101
0010011100000001000010010000010100111110000110110010000001000110000110010000001010010100001001000110
1101010001000011000100000110000100010010000000010101011000011000000100000000100001010010011011000011
0110001011000000000001010100001111000100000001010000000101000101011000000000010001000110100101010010
1000000100100000011100100001110010000000010000101100011001010100010100011001100000000001010000100100
1100110110010011010100000000000010001000000100000101000000100000011110001100000001010100010000101110
0100000000100110111010100000000110000000000000000011010000101111110010000001000101001000100011011000
1100001100000101100100011000000010100000000000000001010001101010010000010010000001001001110001110000
0010001010000100100011000010000000011011001010000000001110000000000001000001100010111111000000010000
1101001001001001001001001100011001100000000010010010000001011000001001101010000000000000111000011100
0000100011001100001011001010100100000001000000010111010100001000010001000001011000000100000110100101
1110111000100100000101000100000100000000000010100010001101001000000011000110010001000010100100100011
0011000110101100010010100101100000000000100000000000001000011100001010010001101100101100100110010110
0010010101000000111010001010000100001100001000001100100000110000000001001010000000010101011100000000
0000111100100001100100001001000000000000001101010010001100001010000000000001110001010100010000011001
1001010000111000100101000001000000001000101000110001010000000001001110100100000001101011101000100000
0101010001010010100000110000100000000000000110000000111001001100000010110000010100101010011010110000
1100110010010010100001000010000000001000000000100000100001000001000011000000100001001000100101000111
0010000000111111011000000101000000001000100000100000000000101000000000000100000110000011110001111010
1111010100010000110000001010001100000000000000100100100000000001100011000010100100001100011000001110
0001010000001000000100110010000101010001111001100000100010000000101010000000000010101000101000011001
0000010000001010100111100110010010100000101000010000000000000000001010000000000010001111000111110001
0100111110000110000000011000010100001000001100000000000000000010100101011001001011001000000100101101
1001010010001101000000000001101110000000010000001000100100001100100000001100011000100100100000110100
0101100000000101100011111001010001010000001000000000000000010001101000100000000000100001110110001000
0100000001101011000000000001100001101000010001000001100001010001001100011000100011000000000000101010
0001111001011100000000100000000000000000000000010000000001100111001000101100111110110000000001000110
1111010101100100000000011000001010000000000000000000001100010000111100010111101001010011101000000001
0000000000000001001111000000111110010110111011101001000000101000000000000000000010000000001001111011
1000010010011101100000011001101001111011000000100000001000001000000100000000000000011111011000001100
0111101110000100011100110000000000000001010000000000001000001010110001010001010111100010010111000000
0000100010001001110001001000010100001000110000100000000000000000001001110110110100011000001100000101
1100000011101100001100000010010011110000000000001000000000001001100010000010001100100110000110001001
0100001000101010011001101000010000000000011000000100001001011000100000100000001011101010000001101000
0100001111000011010110101110111000000000000000101000101000000000000000000100000100010101000110001111
1101100100010000001100000010101100000000000000010010101000000000000000001000111001010001100011011010
0000100011000000011000100110000111110001000100001001100001000000100100011001000000011001000100001100
0011111110011001001110001100000000000000010000000000000000000001110101001100010011000001011101100010
0101000011010000111010000111000100000001100010101000000000000010000000011010010010100110100000100010
1111000000110000010100010100000000110000010000000000010010000001000100000101011100110000010000010111
0010000110100000100001001110010000001001000000011000000010010000000100001101001000101101010001100101
1100010000010110111001000001000010000110010010100000100110100000111000001000000110011001101010000100
0000100001001100101000000111010001110010000001001000101010100000000000101110001001000100011110010000
1111011001100100110000000100000000000011000000001000001000000000001001110000011101001000100001010000
0010101101001011100011010000000000000001010000100000100001000111001100001000000000000110100111011001
0000011010011100000001100000000011000000010110101100001010000000100100100011110011000010000000110110
0000001000010000010001001011001001100100100000010111011111000010010011000000000100010000001000100000
1001111000000000000010000010001011011101111000010100100000000000000001101110000110000101010000011000
1100100111000010010000000000000100100111010001001110000100010001001000100011000011101010001000100010
0001000010010100000100001110010100101000011000000000000110100110000000010101000000000001001011011101
0100100100110011100000110100100100010010110010000010000010010011100000101000000000001100101010000011
1111010100000001001001000100000010010100000101010010100010000010000010000010011101110011100010000010
0010000101111010001100001010000101000111000110000000101011000100000010001111010000000000010001110100
0010000101010101000100010000000010001100010100001011000000100101001010110100100010111001100100011010
1010101100000000001000000000110000000110111101100010100100101001000000010000100100000011010101000100
1011010001100100100001011000000100010100001001000111000110011001000110000010000000001000011011010010
0000010001010100101110010100010000100000001110000101010000001100001101100000110010000000101010011000
0101101010100110101000100000100000000000010001101100111010110000000110000000000000000100010101001111
0000110010111001100100100000111000011101100010001010000110000100010100010000010100100000100000110100
1010100000101101010000010101000000001011011011010001000001000110101100000001101100010000101010001000
0000010100011000110000101010011010010010001010010000010100100100100000110011000101001100000000101010
0001000100010010010011011001100100010011000010101001010111010100010001000010000000100111100100000100
1000111000100001001000001001011000111000010001000001000000100111001010000110000000010000100111110001
1011001000011110000100101011001010001010100111000110010010000000100001110001000001110010010001011100
0001011001000001110001010110100000011101101101000000001000011110110000001000110111000000001001100101
0010010011110010000101000001110011000101000100111011010000010010001000000011101010110100000000001111
0100011101000110010011000101010100101000100001000001010101010010000100101010101001101000001110101000
1011000010001010100100001001001011100100010111011000010010000101000100011010001100010000001010000110
0000000011001000101101000000000110100100011100000000010001001010010101110000001001011101010000100101
0010111010000110000000101100100001111010000001001011011000000011010000100101111000000010010000001111
0010001100010001100000111000010001000111100000000110110100100101110010000100101001000100110110110000
1110000000100111011110010010010010001001001000010100000111010000000000010010010000001010100000011100
1010000010000000000010011000101011000010010101010100100101111110100001010100001001100001001100110111
1101011110011000111000000000100100001010101110011000001000010010110001011010010110010000111000001010
0100100010101001010001111000001101010001000100110000110001100000010110001000111011010010100101001011
0100000001000011010010001001001000110001000111010110000001000001110001101101010010011010010111000110
1100001000000000001010100011011001101100000001110011011000101001011011010001100101000111001000000010
0010100110100000011111100101001010110010100000100110110010111000001100010010100010001001001000101110

"""