Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import queue
H,W=map(int, input().split())

inmap = [input() for _ in range(H)]

q = queue.Queue(10)
q.put((0,0,1))

cood = [(1,0),(-1,0),(0,1),(0,-1)]

res = 0

visited = set([(0,0)])

while not q.empty():
    x,y,cnt=q.get()
    # print(x,y)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            # print(visited)
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)

### FIXED CODE ###

import queue
H,W=map(int, input().split())
inmap = [input() for _ in range(H)]

q = queue.Queue(2500)
q.put((0,0,1))
cood = [(1,0),(-1,0),(0,1),(0,-1)]
res = 0

visited = set((0,0))

while not q.empty():
    x,y,cnt=q.get(False)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)
### BUGGY CODE ###

N = int(input())
S = input().rstrip('#').lstrip('.')
#intS = []
def xor(A,B):
    #print(A)
    #print(B)
    num = 0
    for i in range(len(A)):
        
        if A[i]!=B[i] :
            num = num + 1
    return num
# for s in S :
#     intS.append(0 if s=='.' else 1)
minC = N

mask = ['#' for j in range(len(S) + 1)]
for i in range(len(S) + 1):
    mask[i] = '.'
    c = xor(mask[1::],S)
    if c < minC:
        minC = c

print(minC)
# def dl(_S):
    

#     l = '.'
#     r = '#'
    
#     _S = _S.lstrip(l).rstrip(r)
#     print(_S)
#     if len(_S) == 0:
#         return 0
#     _S2W = _S.lstrip(r)
#     _S2B = _S.rstrip(l)
#     _S2 =  _S2W if len(_S2W) <= len(_S2B) else _S2B
#     return len(_S) - len(_S2) + dl(_S2)
# print(dl(S))






### FIXED CODE ###

_ = input()
S = input()
numc = S.count('.')
numcmin = numc
for s in S:
    if s == '#':
        numc = numc + 1
    else:
        numc = numc -1
        if numc < numcmin:
            numcmin = numc
print(numcmin)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
while len(A)>1:
    p = A[0]
    if len(A)==1:
        ans += 1
    else:
        if A[0] != A[1]:
            A = [j for j in A if j % p !=0]
            ans += 1
        else:
            A = [j for j in A if j % p !=0]
if len(A)==1:
    print(ans+1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
from collections import Counter
AA = Counter(A)
dp = [True]*(A[-1]+1)
ans = 0
for k,v in AA.items():
    if dp[k]==True and v == 1:
        ans += 1
    for i in range(A[-1]//k+1):
        dp[k*i] = False
print(ans)
### BUGGY CODE ###

n = int(input())
fx = [0] * (n + 1)

for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        fx[j] += 1

l = [i * x for i, x in enumerate(fx)]
print(sum(l))

### FIXED CODE ###

n = int(input())

ans = 0
for x in range(1, n + 1):
    ans += (x + n//x * x) * (n // x) / 2
    
print(int(ans))
### BUGGY CODE ###

t = int(input())

def sub(a, b, c, d):
	values = [a]
	i = a
	while (True):
		i = i % b if i > b else i - b
		if i < 0:
			return 'No'
		if i <= c:
			i += d
		if i in values:
			return 'Yes'
		values.append(i)
	return 'No'

def main():
	for i in range(0, t):
		a, b, c, d = map(int, input().split(' '))
		print(sub(a, b, c, d))

main()


### FIXED CODE ###

import fractions

T = int(input())

def solve(A, B, C, D):
    left = A
    if A < B:
        print('No')
        return
    if D < B:
        print('No')
        return
    if C >= B:
        print('Yes')
        return
    g = fractions.gcd(B, D)
    max_mod_b = B - g + (A % g)
    if max_mod_b > C:
        print('No')
    else:
        print('Yes')

for _ in range(T):
    A, B, C, D = map(int, input().split())
    solve(A, B, C, D)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict

def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
for a in As:
    if a == 1:
        continue
    factors = factorization(a)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod
print((lcm*a)%mod)


### FIXED CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline
import numpy as np
def solve():
  n = int(input())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
  q,k = (int(i) for i in input().split())
  d = np.array(d)
  d = dijkstra(d,indices = k-1)

  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d[x-1] + d[y-1]))

solve()

### FIXED CODE ###


import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = visit
      d2[place] = dist
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np]:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()
### BUGGY CODE ###

s=input()
k=int(input())
count=0
for i in s:
    count+=int(i)**(5*(10**10))
    if count>=k:
        print(i)
        break

### FIXED CODE ###

s=input()
k=int(input())
count=0
ans=''
for i in range(k):
    if s[i]=='1':
        count+=1
    else:
        ans=s[i]
        break
print(1 if count==k else ans)
### BUGGY CODE ###

n, m = map(int, input().split())
keys = []
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
keys = []
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

from collections import Counter

a,b = map(int,input().split())

def sosuu(a):
    sosuu_list = set()
    while 1:
        flag = True
        for i in range(2,a+1):
            if a % i == 0 and a != i:
                a = a//i
                sosuu_list.add(i)
                flag = False
                break
        if flag:
            sosuu_list.add(a)
            return sosuu_list

a = sosuu(a)
# print(a)
ans = 1
for aa in a:
    if b % aa == 0 and aa != 1:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
from fractions import gcd

a,b = map(int,input().split())

g = gcd(a,b)

def sosuu(a):
    sosuu_list = set()
    sosuu_list.add(1)
    i = 2
    while 1:
        flag = True
        while a >= i*i:
            if a % i == 0:
                # print(a,i)
                a = a//i
                sosuu_list.add(i)
                flag = False
            else:
                i += 1
        if flag:
            sosuu_list.add(a)
            return sosuu_list
        i += 1

a = sosuu(g)
print(len(a))
### BUGGY CODE ###

n,k = map(int,input().split())
lst = list(map(int,input().split()))

typ = list(set(lst))
NumList = []
for i in range(len(typ)):
    c = lst.count(typ[i])
    NumList.append([typ[i],c])
NumList.sort(key = lambda x:x[1])
cnt = 0
for i in range(len(typ) - k):
    cnt += NumList[i][1]
print(cnt)


### FIXED CODE ###

from collections import Counter

n,k = map(int,input().split())
lst = list(map(int,input().split()))
typ = list(set(lst))

ans = 0
NumList = Counter(lst)
num = sorted(NumList.items(),key=lambda x:x[1])
for l in range(len(typ)-k):
    ans += num[l][1]
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
a = deque(a)
circle = []
circle.append(a.popleft())

ans = 0
while a:
    nex = a.popleft()
    mx = 0
    for i in range(len(circle)):
        if mx <= min(circle[i-1], circle[i]):
            mx = min(circle[i-1], circle[i])
            mx_idx = i
    ans += mx
    circle.insert(mx_idx, nex)
print(ans)


### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(int, input().split()))

a.sort()
ans = 0
for i in range(1, n):
    ans += a[n-i//2-1]
print(ans)
### BUGGY CODE ###

mod = 10 ** 9 + 7
pows = [1] * 66
for i in range(65):
    pows[i + 1] = (pows[i] * (i + 1)) % mod


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def c(a, b):
    return pows[a] * pow(pows[a - b], mod - 2, mod) * pow(pows[b], mod - 2, mod) % mod


def p(N, a):
    return a * (N - a) % mod


def main():
    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        b = format(a, "065b")[::-1]
        for i in range(65):
            num[i] += int(b[i])

    res = 0
    for i in range(65):
        res = (res + pow(2, i, mod) * p(N, num[i])) % mod

    print(res % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    pows = [1] * 66
    for i in range(65):
        pows[i + 1] = (pows[i] * 2) % mod

    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

# https://hiramekun.hatenablog.com/entry/2019/06/18/184256

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]  # (i,j)で丁度終わる文字列数
    dp[0][0] = 0
    dp[0][1] = 0
    dp[1][0] = 0

    acc = [[0] * (M + 1) for _ in range(N + 1)]
    acc[0][0] = 0
    acc[0][1] = 0
    acc[1][0] = 0

    for i, si in enumerate(s, 1):
        for j, ti in enumerate(t, 1):
            if si == ti:
                dp[i][j] = acc[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            acc[i][j] = (acc[i - 1][j] + acc[i][j - 1] + dp[i][j] - acc[i - 1][j - 1]) % MOD

    ans = acc[N][M] + 1  # ("","")のケース

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://hiramekun.hatenablog.com/entry/2019/06/18/184256

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]  # (i,j)で丁度終わる文字列数
    dp[0][0] = 0
    dp[0][1] = 0
    dp[1][0] = 0

    acc = [[0] * (M + 1) for _ in range(N + 1)]
    acc[0][0] = 0
    acc[0][1] = 0
    acc[1][0] = 0

    for i, si in enumerate(s, 1):
        for j, ti in enumerate(t, 1):
            if si == ti:
                dp[i][j] = acc[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            acc[i][j] = (acc[i - 1][j] + acc[i][j - 1] + dp[i][j] - acc[i - 1][j - 1]) % MOD

    ans = acc[N][M] + 1  # ("","")のケース

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

class ColorMgmt:
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
    
    def get_color(self, v):
        for i in range(1, N):
            if not i in self.colors_hash[v]:
                return i
        return N


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])


### FIXED CODE ###

class ColorMgmt:
    from heapq import heappop, heappush
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        while self.next_colors[v] in self.colors_hash[v]:
            self.next_colors[v] += 1
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])
### BUGGY CODE ###

N=int(input())
A = [int(x) for x in input().split()]

ans=1
if 0 in A:
    ans = 0
else:
    for a in A:
        if a > 10**18:
            ans = -1
        else:
            ans *= a
            if ans > 10**18:
                ans = -1
print(ans)

                


### FIXED CODE ###

N=int(input())
A = [int(x) for x in input().split()]

ans=1
if 0 in A:
    ans = 0
else:
    A.sort(reverse=True)
    for a in A:
        if a > 10**18:
            ans = -1
            break
        else:
            ans *= a
            if ans > 10**18:
                ans = -1
                break
print(ans)
### BUGGY CODE ###

in_ = [int(i) for i in input().split()]
L = in_[0]
R = in_[1]
mod_min = 100000
# L = L % 2019
# R = R % 2019
# tab = [[-1 for r in range(R+1)] for l in range(L+1)]
# print(tab)
i_list = []
j_list = []
for i in range(L, R):
    i_mod = i % 2019
    for j in range(i+1, R+1):
            j_mod = j % 2019
            mod = i_mod * j_mod % 2019
            if mod < mod_min:
                mod_min = mod
                if mod_min == 0:
                    break
print(mod_min)

### FIXED CODE ###

in_ = [int(i) for i in input().split()]
L = in_[0]
R = in_[1]
mod_min = 100000
# L = L % 2019
# R = R % 2019
# tab = [[-1 for r in range(R+1)] for l in range(L+1)]
# print(tab)
i_list = []
j_list = []
for i in range(L, R):
    i_mod = i % 2019
    for j in range(i+1, R+1):
            j_mod = j % 2019
            mod = i_mod * j_mod % 2019
            if mod < mod_min:
                mod_min = mod
                if mod_min == 0:
                    break
    if mod_min == 0:
        break
print(mod_min)
### BUGGY CODE ###

n=int(input())
s=input()
ans=[]
ecnt=list(s).count("E")
for i in range(n):
    left=list(s[:i]).count("W")
    right=ecnt-(i-left)
    ans.append(left+right)
print(min(ans))

### FIXED CODE ###

n=int(input())
s=input()
ans=[]
alle=list(s).count("E")
allw=n-alle
ecnt=wcnt=0
for i in range(n):
    if s[i] == "W":
        ans.append(wcnt+alle-ecnt)
        wcnt+=1
    else:
        ans.append(wcnt+alle-ecnt-1)
        ecnt+=1
print(min(ans))
### BUGGY CODE ###

import math
N = int(input())
ans = 0
upper = int(math.sqrt(N))
for n in range(1, N+1):
    ans = 0
    for x in range(1, upper):
        for y  in range(1, upper):
            z = 0
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v > n:
                break
            for z in range(1, upper):
                v = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if  v == n:
                    ans += 1
                    #print((x, y, z))
                elif v > n:
                    break
    print(ans)

### FIXED CODE ###

import math
N = int(input())
ans = 0
num = {i:0 for i in range(1, N+1)}
upper = int(math.sqrt(N)) + 1
for x in range(1, upper):
    for y  in range(1, upper):
        z = 1
        v = x**2 + y**2 + z**2 + x*y + y*z + z*x
        if v > N:
            break
        for z in range(1, upper):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v in num.keys():
                num[v] += 1
            if v > N:
                break
for n in range(1, N+1):
    print(num[n])
### BUGGY CODE ###

N, M, Q = map(int, input().split())

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]
ans = [[0 for i in range(509)] for j in range(509)]

for i in range(M):
  p, q = map(int, input().split())
  a[p][q] += 1

for i in range(1,N+1):
  for j in range(i,N+1):
    sum[i][j] = sum[i][j-1] + a[i][j]

for i in range(1,N+1):
  for j in range(i,N+1):
    for k in range(i,j+1):
      ans[i][j] += sum[k][j] - sum[k][i-1]

for i in range(Q):
  p, q = map(int, input().split())
  #ans = 0
  #for j in range(p,q+1):
  #  ans += sum[j][q] - sum[j][p-1]
  print(ans[p][q])


### FIXED CODE ###

N, M, Q = map(int, input().split())

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]
ans = [[0 for i in range(509)] for j in range(509)]

for i in range(M):
  p, q = map(int, input().split())
  a[p][q] += 1

for i in range(1,N+1):
  for j in range(i,N+1):
    sum[i][j] = sum[i][j-1] + a[i][j]

for i in range(1,N+1):
  for j in range(i,N+1):
    for k in range(i,j+1):
      ans[i][j] += sum[k][j] - sum[k][i-1]

for i in range(Q):
  p, q = map(int, input().split())
  #ans = 0
  #for j in range(p,q+1):
  #  ans += sum[j][q] - sum[j][p-1]
  print(ans[p][q])