/* paiza POH! vol.2
* result:
* http://p...content-available-to-author-only...a.jp/poh/paizen/result/c1dffe837f21e4c97badc6e536a27a16
* author: Leonardone @ NEETSDKASU
*/
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
{
Paiza.getInstance().resolve(new MyResolver());
}
}
{
private int[][] space2right = null;
private int[][] space2bottom = null;
private int[][] result = null;
@Override
public void setHome(Paiza.Home home) {
super.setHome(home);
result = new int[301][301];
space2right = new int[home.getH()][home.getW()];
for (int y = 0; y < home.getH(); y++) {
int count = 0;
for (int x = home.getW() - 1; x >= 0; x--) {
if (home.isSpace(x, y)) {
count++;
} else {
count = 0;
}
space2right[y][x] = count;
}
}
space2bottom = new int[home.getH()][home.getW()];
for (int x = 0; x < home.getW(); x++) {
int count = 0;
for (int y = home.getH() - 1; y >= 0; y--) {
if (home.isSpace(x, y)) {
count++;
} else {
count = 0;
}
space2bottom[y][x] = count;
}
}
}
@Override
public int resolve(Paiza.Widget widget) {
if (result[widget.getS()][widget.getT()] > 0) {
return result[widget.getS()][widget.getT()] - 1;
}
int count;
if (widget.getS() > widget.getT()) {
count = resolve2bottom(widget);
} else {
count = resolve2right(widget);
}
result[widget.getS()][widget.getT()] = count + 1;
return count;
}
private int resolve2right(Paiza.Widget widget) {
int count = 0;
for (int y = 0; y <= home.getH() - widget.getS(); y++) {
for (int x = 0; x <= home.getW() - widget.getT(); x++) {
if (space2bottom[y][x] >= widget.getS()) {
boolean placeable = true;
for (int dy = 0; placeable && dy < widget.getS(); dy++) {
if (space2right[y + dy][x] < widget.getT()) {
placeable = false;
x += space2right[y + dy][x];
}
}
if (placeable) {
count++;
}
} else if (space2right[y][x] < widget.getT()) {
x += space2right[y][x];
}
}
}
return count;
}
private int resolve2bottom(Paiza.Widget widget) {
int count = 0;
for (int x = 0; x <= home.getW() - widget.getT(); x++) {
for (int y = 0; y <= home.getH() - widget.getS(); y++) {
if (space2right[y][x] >= widget.getT()) {
boolean placeable = true;
for (int dx = 0; placeable && dx < widget.getT(); dx++) {
if (space2bottom[y][x + dx] < widget.getS()) {
placeable = false;
y += space2bottom[y][x + dx];
}
}
if (placeable) {
count++;
}
} else if (space2bottom[y][x] < widget.getS()) {
y += space2bottom[y][x];
}
}
}
return count;
}
}
{
protected Paiza.Home home;
public void setHome(Paiza.Home home) {
this.home = home;
}
public abstract int resolve(Paiza.Widget widget);
}
final class Paiza
{
{
protected Paiza.Home home;
public void setHome(Paiza.Home home) {
this.home = home;
}
public abstract int resolve(Paiza.Widget widget);
}
public static Paiza getInstance
() throws java.
lang.
Exception { if (paiza == null) {
paiza = new Paiza();
}
return paiza;
}
public void resolve
(Resolver resolver
) { init(resolver);
for (Widget widget : widgets) {
answer(resolver.resolve(widget));
}
flush();
}
public final class Home
{
private final int H;
private final int W;
private int[][] display;
private Home(int H, int W) {
this.H = H;
this.W = W;
display = new int[H][W];
}
private void setDisplay
(int x,
int y,
int e
) throws java.
lang.
Exception { if (x < 0 || x >= W) {
}
if (y < 0 || y >= H) {
}
if (e != 0 && e != 1) {
}
display[y][x] = e;
}
public int getH() {
return H;
}
public int getW() {
return W;
}
public boolean isSpace(int x, int y) {
if (x < 0 || y < 0 || x >= W || y >= H) {
return false;
}
return display[y][x] == 0;
}
}
public final class Widget
{
private final int s;
private final int t;
private Widget(int s, int t) {
this.s = s;
this.t = t;
}
public int getS() {
return s;
}
public int getT() {
return t;
}
}
private static Paiza paiza = null;
private Home home;
private ArrayList<Widget> widgets;
String[] hw
= in.
readLine().
split(" "); for (int y = 0; y < home.getH(); y++) {
for (int x = 0; x < home.getW(); x++) {
home.setDisplay(x, y, (int)(line.charAt(x) - '0'));
}
}
int N
= Integer.
parseInt(in.
readLine()); widgets = new ArrayList<Widget>(N);
for (int i = 0; i< N; i++) {
String[] st
= in.
readLine().
split(" "); widgets.
add(new Widget
(Integer.
parseInt(st
[0]),
Integer.
parseInt(st
[1]))); }
}
private StringBuilder output = null;
private static final String NEWLINE
= System.
getProperty("line.separator");
resolver.setHome(home);
output = new StringBuilder(widgets.size() * 6);
}
private void answer(int count) {
output.append(count);
output.append(NEWLINE);
}
private void flush() {
}
}