/* paiza POH!vol.2
* result:
* http://p...content-available-to-author-only...a.jp/poh/paizen/result/a653bd2a9ffbe6879c2fb2c7db6f249f
* author: Leonardone @ NEETSDKASU
*/
#include <stdio.h>
#define SIZE (9000000)
char input[SIZE];
char *ptr = input;
int getInt(void) {
int v = 0;
while (*ptr < '0' || *ptr > '9') ++ptr;
while (*ptr >= '0' && *ptr <= '9')
{
v = 10 * v + (int)(*ptr - '0');
++ptr;
}
return v;
}
char getChar(void) {
while (*ptr < '0' || *ptr > '9') ++ptr;
return *ptr++;
}
void putInt(int v) {
if (v < 10) {
} else {
putInt(v / 10);
}
}
int home[310][310];
int hoge[310][310];
int result[310][310];
int main(void) {
int H, W, N, s, t;
int x, y, c, i;
int hx, hy, hxe, hye;
int count, dy, dx;
char ch;
fread(input
, sizeof(char), SIZE
, stdin
); H = getInt();
W = getInt();
for (y = 0; y < H; ++y) {
c = 0;
for (x = 0; x < W; ++x) {
ch = getChar();
if (ch == '0') {
c++;
if (y) {
hoge[y][x] = hoge[y - 1][x] + 1;
} else {
hoge[y][x] = 1;
}
} else {
c = 0;
hoge[y][x] = 0;
}
home[y][x] = c;
}
}
N = getInt();
for (i = 0; i < N; ++i) {
s = getInt();
t = getInt();
if (s > H || t > W) {
continue;
}
if (result[s][t]) {
putInt(result[s][t] - 1);
continue;
}
hye = s - 1;
hxe = t - 1;
count = 0;
if (W > H) {
for (hy = H - 1; hy >= hye; --hy) {
for (hx = W - 1; hx >= hxe; --hx) {
if (home[hy][hx] < t) {
hx -= home[hy][hx];
continue;
}
if (hoge[hy][hx] < s) {
continue;
}
for (dy = 1; dy < s; ++dy) {
y = hy - dy;
if (y < 0) {
break;
}
if (home[y][hx] < t) {
break;
}
}
if (dy == s) {
count++;
}
}
}
} else {
for (hx = W - 1; hx >= hxe; --hx) {
for (hy = H - 1; hy >= hye; --hy) {
if (home[hy][hx] < t) {
continue;
}
if (hoge[hy][hx] < s) {
hy -= hoge[hy][hx];
continue;
}
for (dy = 1; dy < s; ++dy) {
y = hy - dy;
if (y < 0) {
break;
}
if (home[y][hx] < t) {
break;
}
}
if (dy == s) {
count++;
}
}
}
}
putInt(count);
result[s][t] = count + 1;
}
return 0;
}
LyogcGFpemEgUE9IIXZvbC4yCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL3BhaXplbi9yZXN1bHQvYTY1M2JkMmE5ZmZiZTY4NzljMmZiMmM3ZGI2ZjI0OWYKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIFNJWkUgKDkwMDAwMDApCgpjaGFyIGlucHV0W1NJWkVdOwpjaGFyICpwdHIgPSBpbnB1dDsKCmludCBnZXRJbnQodm9pZCkgewoJaW50IHYgPSAwOwoJd2hpbGUgKCpwdHIgPCAnMCcgfHwgKnB0ciA+ICc5JykgKytwdHI7Cgl3aGlsZSAoKnB0ciA+PSAnMCcgJiYgKnB0ciA8PSAnOScpCgl7CgkJdiA9IDEwICogdiArIChpbnQpKCpwdHIgLSAnMCcpOwoJCSsrcHRyOwoJfQoJcmV0dXJuIHY7Cn0KCmNoYXIgZ2V0Q2hhcih2b2lkKSB7Cgl3aGlsZSAoKnB0ciA8ICcwJyB8fCAqcHRyID4gJzknKSArK3B0cjsKCXJldHVybiAqcHRyKys7Cn0KCnZvaWQgcHV0SW50KGludCB2KSB7CglpZiAodiA8IDEwKSB7CgkJcHV0Y2hhcignMCcgKyAoY2hhcil2KTsKCX0gZWxzZSB7CgkJcHV0SW50KHYgLyAxMCk7CgkJcHV0Y2hhcignMCcgKyAoY2hhcikodiAlIDEwKSk7Cgl9Cn0KCmludCBob21lWzMxMF1bMzEwXTsKaW50IGhvZ2VbMzEwXVszMTBdOwppbnQgcmVzdWx0WzMxMF1bMzEwXTsKCmludCBtYWluKHZvaWQpIHsKCWludCBILCBXLCBOLCBzLCB0OwoJaW50IHgsIHksIGMsIGk7CglpbnQgaHgsIGh5LCBoeGUsIGh5ZTsKCWludCBjb3VudCwgZHksIGR4OwoJY2hhciBjaDsKCQoJZnJlYWQoaW5wdXQsIHNpemVvZihjaGFyKSwgU0laRSwgc3RkaW4pOwoJSCA9IGdldEludCgpOwoJVyA9IGdldEludCgpOwoJCglmb3IgKHkgPSAwOyB5IDwgSDsgKyt5KSB7CgkJYyA9IDA7CgkJZm9yICh4ID0gMDsgeCA8IFc7ICsreCkgewoJCQljaCA9IGdldENoYXIoKTsKCQkJaWYgKGNoID09ICcwJykgewoJCQkJYysrOwoJCQkJaWYgKHkpIHsKCQkJCQlob2dlW3ldW3hdID0gaG9nZVt5IC0gMV1beF0gKyAxOwoJCQkJfSBlbHNlIHsKCQkJCQlob2dlW3ldW3hdID0gMTsKCQkJCX0KCQkJfSBlbHNlIHsKCQkJCWMgPSAwOwoJCQkJaG9nZVt5XVt4XSA9IDA7CgkJCX0KCQkJaG9tZVt5XVt4XSA9IGM7CgkJfQoJfQoJCglOID0gZ2V0SW50KCk7CgkKCWZvciAoaSA9IDA7IGkgPCBOOyArK2kpIHsKCQlzID0gZ2V0SW50KCk7CgkJdCA9IGdldEludCgpOwoJCQoJCWlmIChzID4gSCB8fCB0ID4gVykgewoJCQlwdXRjaGFyKCcwJyk7CgkJCXB1dGNoYXIoJ1xuJyk7CgkJCWNvbnRpbnVlOwoJCX0KCQkKCQlpZiAocmVzdWx0W3NdW3RdKSB7CgkJCXB1dEludChyZXN1bHRbc11bdF0gLSAxKTsKCQkJcHV0Y2hhcignXG4nKTsKCQkJY29udGludWU7CgkJfQoJCQoJCWh5ZSA9IHMgLSAxOwoJCWh4ZSA9IHQgLSAxOwoJCWNvdW50ID0gMDsKCQlpZiAoVyA+IEgpIHsKCQkJZm9yIChoeSA9IEggLSAxOyBoeSA+PSBoeWU7IC0taHkpIHsKCQkJCWZvciAoaHggPSAgVyAtIDE7IGh4ID49IGh4ZTsgLS1oeCkgewoJCQkJCWlmIChob21lW2h5XVtoeF0gPCB0KSB7CgkJCQkJCWh4IC09IGhvbWVbaHldW2h4XTsKCQkJCQkJY29udGludWU7CgkJCQkJfQoJCQkJCWlmIChob2dlW2h5XVtoeF0gPCBzKSB7CgkJCQkJCWNvbnRpbnVlOwoJCQkJCX0KCQkJCQlmb3IgKGR5ID0gMTsgZHkgPCBzOyArK2R5KSB7CgkJCQkJCXkgPSBoeSAtIGR5OwoJCQkJCQlpZiAoeSA8IDApIHsKCQkJCQkJCWJyZWFrOwoJCQkJCQl9CgkJCQkJCWlmIChob21lW3ldW2h4XSA8IHQpIHsKCQkJCQkJCWJyZWFrOwoJCQkJCQl9CgkJCQkJfQoJCQkJCWlmIChkeSA9PSBzKSB7CgkJCQkJCWNvdW50Kys7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfSBlbHNlIHsKCQkJZm9yIChoeCA9ICBXIC0gMTsgaHggPj0gaHhlOyAtLWh4KSB7CgkJCQlmb3IgKGh5ID0gSCAtIDE7IGh5ID49IGh5ZTsgLS1oeSkgewoJCQkJCWlmIChob21lW2h5XVtoeF0gPCB0KSB7CgkJCQkJCWNvbnRpbnVlOwoJCQkJCX0KCQkJCQlpZiAoaG9nZVtoeV1baHhdIDwgcykgewoJCQkJCQloeSAtPSBob2dlW2h5XVtoeF07CgkJCQkJCWNvbnRpbnVlOwoJCQkJCX0KCQkJCQlmb3IgKGR5ID0gMTsgZHkgPCBzOyArK2R5KSB7CgkJCQkJCXkgPSBoeSAtIGR5OwoJCQkJCQlpZiAoeSA8IDApIHsKCQkJCQkJCWJyZWFrOwoJCQkJCQl9CgkJCQkJCWlmIChob21lW3ldW2h4XSA8IHQpIHsKCQkJCQkJCWJyZWFrOwoJCQkJCQl9CgkJCQkJfQoJCQkJCWlmIChkeSA9PSBzKSB7CgkJCQkJCWNvdW50Kys7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfQoJCXB1dEludChjb3VudCk7CgkJcHV0Y2hhcignXG4nKTsKCQlyZXN1bHRbc11bdF0gPSBjb3VudCArIDE7Cgl9CgkKCXJldHVybiAwOwp9Cg==