def F_generate(h,w,a): #aは2次元配列 da=[[0]*w for j in range(h)] da[0][0]=a[0][0] for i in range(1,w): da[0][i]=da[0][i-1]+a[0][i] for i in range(1,h): cnt_w=0 for j in range(w): cnt_w+=a[i][j] da[i][j]=da[i-1][j]+cnt_w return da def F_calc(F,p,q,x,y): #Fが2次元累積和の配列,左上のマスが(p,q),右下のマスが(x,y)の区間和 if p>x or q>y: return 0 if p==0 and q==0: return F[x][y] if p==0: return F[x][y]-F[x][q-1] if q==0: return F[x][y]-F[p-1][y] return F[x][y]-F[p-1][y]-F[x][q-1]+F[p-1][q-1] N,M=map(int,input().split()) F=[list(map(int,input().split())) for _ in range(M)] Q=[list(map(lambda x:int(x)-1,input().split())) for _ in range(N)] da=F_generate(M,M,F) ans=[[0]*(M+1) for _ in range(M+1)] for x1 in range(M): for y1 in range(M): for x2 in range(x1,M): for y2 in range(y1,M): if F_calc(da,x1,y1,x2,y2)==0: ans[x1][y1]+=1 ans[x1][y2+1]-=1 ans[x2+1][y1]-=1 ans[x2+1][y2+1]+=1 for i in range(M): for j in range(M): ans[i][j+1]+=ans[i][j] for j in range(M): for i in range(M): ans[i+1][j]+=ans[i][j] for x,y in Q: print(ans[x][y])