paizen_2.py

# -*- coding: utf-8 -*-

def func():
    h, w = map(int, raw_input().split())

    display = []
    for i in xrange(h):
        row = raw_input()
        display.append(row)

    lenmap = [[0 for i in xrange(w)] for j in xrange(h)]
    for j in xrange(h):
        for i in xrange(w):
            
            dxdy = []
            flag = False

            prev = [10000, 10000]
            maxdx = 10000
            for dy in xrange(h-j):
                counter = -1
                for dx in xrange(w-i):
                    if display[j+dy][i+dx] == '1':
                        break
                    else:
                        counter += 1
                maxdx = min(maxdx, counter)
                if maxdx < 0:
                    flag = True
                    break

                if prev[0] < dy and prev[1] <= maxdx:
                    dxdy.remove(prev)
                dxdy.append([dy, maxdx])
                prev = [dy, maxdx]

            lenmap[j][i] = dxdy
            if flag == True:
                continue

    n = int(raw_input())

    for k in xrange(n):
        s, t = map(int, raw_input().split())

        count = 0

        for j in xrange(h-s+1):

            for i in xrange(w-t+1):

                for [y, x] in lenmap[j][i]:
                    if s <= y + 1 and t <= x + 1:
                        count += 1
                        break

        print count
    
    return None

if __name__ == '__main__':
    func()