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

from collections import Counter
def min_distance(i,j):
    return min(abs(i-j),abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j))
               
n,x,y=list(map(int,input().split()))
x=x-1
y=y-1
dp=[]
for i in range(n):
    for j in range(n):
        dp.append(min_distance(i,j))
dic=Counter(dp)
for i in range(1,n):
    print(int(dic[i]/2))
    
        
     

### FIXED CODE ###

from collections import Counter
def min_distance(i,j):
    return min(abs(i-j),abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j))
               
n,x,y=list(map(int,input().split()))
x=x-1
y=y-1
dp=[]
for i in range(n-1):
    for j in range(i+1,n):
        dp.append(min_distance(i,j))
dic=Counter(dp)
for i in range(1,n):
    print(int(dic[i]))
### BUGGY CODE ###

import sys
N, M, L = map(int, input().split())
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])


# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
for k in range(N):
    for i in range(N):
        for j in range(N):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = map(int, sys.stdin.readline().split())
    s, t = s - 1, t - 1
    print(E[s][t] - 1 if E[s][t] != float('inf') else - 1)


### FIXED CODE ###

import sys
from scipy.sparse.csgraph import floyd_warshall
N, M, L = map(int, input().split())
INF = 10 ** 9 + 1
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
G = floyd_warshall(G)


# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
E = floyd_warshall(E)


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = map(int, sys.stdin.readline().split())
    s, t = s - 1, t - 1
    print(int(E[s][t] - 1) if E[s][t] != float('inf') else - 1)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
p = []
for i in a:
    for j in b:
        p.append(i+j)
p.sort(reverse=True)
p = p[:min(3001, x*y*z+1)]
q = []
for i in p:
    for j in c:
        q.append(i+j)
q.sort(reverse=True)
for i in range(k):
    print(q[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
p = []
for i in a:
    for j in b:
        p.append(i+j)
p.sort(reverse=True)
p = p[:min(3001, x*y*z+1)]
q = []
for j in c:
    for i in p:
        q.append(i+j)
q.sort(reverse=True)
for i in range(k):
    print(q[i])
### BUGGY CODE ###

N = int(input())
*A, = map(int, input().split())
now = 1
for i in A:
    now *= i
if now > 10**18:
    print(-1)
else:
    print(now)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
now = 1
if A.count(0) == 0:
    for i in A:
        now *= i
        if now > 10**18:
            now = -1
            break
else:
    now = 0
print(now)
### BUGGY CODE ###

H, N = (int(i) for i in input().split())
A = []
B = []
for i in range(N):
    a, b = (int(j) for j in input().split())
    A.append(a)
    B.append(b)
A_max = max(A)

DP = [0]
for i in range(1, H+A_max):
    dp = float('inf')
    for a, b in zip(A,B):
        if i-a>=0:
            dp = min(dp, DP[i-a] + b)
    DP.append(dp)
print(min(DP[H:]))

### FIXED CODE ###

H, N = (int(i) for i in input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = (int(j) for j in input().split())
A_max = max(A)

DP = [0]*(H+A_max)
for i in range(1, H+A_max):
    dp = float('inf')
    for a, b in zip(A,B):
        if i-a>=0:
            dp = min(dp, DP[i-a] + b)
    DP[i] = dp
print(min(DP[H:]))
### BUGGY CODE ###

H, N  = map(int, input().split())
# hitpoint H
# waza N
As = [] # damage
Bs = [] # MP comsumptions
for i in range(N):
    a,b = map(int, input().split())
    As.append(a)
    Bs.append(b)

"""
dp[i][j] = i番目までの魔法を見たとき、ダメージがちょうどjになる最小値
"""
INF = 10**10
M = 21000
dp = [[INF]*M for i in range(N+1)]
dp[0][0] = 0
for i,(a,b) in enumerate(zip(As,Bs)):
    dp[i+1][:] = dp[i][:]
    for j in range(H):        
        dp[i+1][j+a] = min(dp[i][j+a], dp[i+1][j]+b)
        # print(i,j,"ab",a,b,"dp",dp[i][j],dp[i][j+1],dp[i][j]+b)
print(min(dp[N][H:]))


### FIXED CODE ###

H, N  = map(int, input().split())
# hitpoint H
# waza N
As = [] # damage
Bs = [] # MP comsumptions
for i in range(N):
    a,b = map(int, input().split())
    As.append(a)
    Bs.append(b)

"""
dp[i][j] = i番目までの魔法を見たとき、ダメージがちょうどjになる最小値
"""
INF = 10**10
M = 21000
dp = [[INF]*M for i in range(N+1)]
dp[0][0] = 0
for i,(a,b) in enumerate(zip(As,Bs)):
    dp[i+1][:] = dp[i][:]
    for j in range(H):        
        dp[i+1][j+a] = min(dp[i][j+a], dp[i+1][j]+b)
        # print(i,j,"ab",a,b,"dp",dp[i][j],dp[i][j+1],dp[i][j]+b)
print(min(dp[N][H:]))
### BUGGY CODE ###

L, R = [int(i) for i in input().split()]
min_mod = (L * R) % 2019 
for i in range(L, R):
    for j in range(i+1,R+1):
        if min_mod > (i * j) % 2019:
            min_mod =(i * j) % 2019
            
print(min_mod)


### FIXED CODE ###

L, R = [int(i) for i in input().split()]
min_mod = (L * R) % 2019 

if R - L > 2019:
    min_mod = 0
else :
    for i in range(L, R):
        for j in range(i+1,R+1):
            if min_mod > (i * j) % 2019:
                min_mod =(i * j) % 2019
                if min_mod == 0:
                    break
print(min_mod)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W,K = map(int,readline().split())
S = np.array([list(line.rstrip()) for line in readlines()]).astype(np.int8) - ord('0')

# 下から上の順に
S = S[::-1].T

def drop(S):
    for i in range(W):
        col = S[i]
        S[i] = drop_col(col)

def drop_col(col):
    x = np.zeros(H,np.int8)
    nonzero = col[col != 0]
    x[:len(nonzero)] = nonzero
    return x

def cnt_connection(S):
    # 横につながっている個数
    x = np.ones_like(S)
    equal = (S[:-1] == S[1:])
    for i in range(1,W):
        x[i] = x[i-1] * equal[i-1] + 1
    for i in range(W-2,-1,-1):
        x[i][equal[i]] = x[i+1][equal[i]]
    return x

def simulate(S,turn):
    # 落とす -> 消去、で1セット
    drop(S)
    conn = cnt_connection(S)
    remove = (conn >= K)
    before = S.sum()
    S *= (~remove)
    after = S.sum()
    if before == after:
        # 消えなかった
        return 0
    else:
        x = simulate(S,turn+1)
        return x + ((before - after) << turn)

def calc(i,j):
    T = S.copy()
    T[j,i] = 0
    return simulate(T,0)

answer = max(calc(i,j) for i in range(H) for j in range(W))
print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import time
start = time.time()

import numpy as np

H,W,K = map(int,readline().split())
S = np.array([list(line.rstrip()) for line in readlines()]).astype(np.int8) - ord('0')

# 下から上の順に
S = S[::-1].T

def drop(S):
    for i in range(W):
        col = S[i]
        S[i] = drop_col(col)

def drop_col(col):
    x = np.zeros(H,np.int8)
    nonzero = col[col != 0]
    x[:len(nonzero)] = nonzero
    return x

def cnt_connection(S):
    # 横につながっている個数
    x = np.ones_like(S)
    equal = (S[:-1] == S[1:])
    for i in range(1,W):
        x[i] = x[i-1] * equal[i-1] + 1
    for i in range(W-2,-1,-1):
        x[i][equal[i]] = x[i+1][equal[i]]
    return x

def simulate(S,turn):
    # 落とす -> 消去、で1セット
    drop(S)
    conn = cnt_connection(S)
    remove = (conn >= K)
    before = S.sum()
    S *= (~remove)
    after = S.sum()
    if before == after:
        # 消えなかった
        return 0
    else:
        x = simulate(S,turn+1)
        return x + ((before - after) << turn)

def calc(j):
    T = S.copy()
    T[j,0] = 0
    return simulate(T,0)

answer = 0
for i in range(H):
    x = max(calc(j) for j in range(W))
    if answer < x:
        answer = x
    H -= 1
    S = S[:,1:]
    if time.time() - start > 0.9:
        break
print(answer)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read
 

# n,m = map(int,input().split())

# a = list(map(int, input().split()))  # n個の文字列がリストに格納される

N = int(input())

A = list(map(int, input().split()))  # n個の文字列がリストに格納される

for i in range(N-1):
    print(A.count(i+1))
    while i+1 in A:
        A.remove(i+1)

print('0')

### FIXED CODE ###

N = int(input())

A = list(map(int, input().split()))  # n個の文字列がリストに格納される

ans = [0] * N

for a in A:
    ans[a-1] += 1

print(*ans,sep='\n')
### BUGGY CODE ###

import bisect
def LIS(seq):
    dp = [seq[0]]
    for e in seq:
        if e > dp[len(dp)-1]:
            dp.append(e)
        else:
            dp[bisect.bisect_left(dp, e)] = e
    return dp

N = int(input())
seq = []
for _ in range(N):
    seq.append(int(input()))

col_num = 0
while seq:
    dp = LIS(seq)
    ind = 0
    _seq = []
    for s in seq:
        if ind < len(dp) and s == dp[ind]:
            ind += 1
        else:
            _seq.append(s)
    seq = _seq
    col_num += 1
    
print(col_num)

### FIXED CODE ###

from collections import deque
import bisect

N = int(input())
table = deque()
for n in range(N):
    a = int(input())
    if n == 0:
        table.append(a)
    else:
        if a <= table[0]:
            table.appendleft(a)
        else:
            table[bisect.bisect_left(table, a)-1] = a
            
print(len(table))
### BUGGY CODE ###

s = str(input())

num_moto = int(len(s))

while True:
    if s.find('10') == -1 and s.find('01') == -1:
        break
    if int(len(s)) == 0:
        break
    s = s.replace('10','')
    s = s.replace('01','')
    
num_kekka = int(len(s))
print(num_moto - num_kekka)

### FIXED CODE ###

s = input()
count_0 = s.count('0')
count_1 = s.count('1')
print(2*min(count_0,count_1))
### BUGGY CODE ###

h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

for cnt in range(h+w):
    c = []
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y != 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y != h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x != 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x != w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    if len(c) == 0:
        print(cnt)
        break
    b = c

### FIXED CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
q = deque([])
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            q.append([j, i, 0])

depth_now = 0
depth = 0
count = 0
while len(q) > 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    depth = p[2]
    if x - 1 >= 0 and M[y][x-1] == '.':
        q.append([x-1, y, depth+1])
        M[y][x-1] = '#'
    if x + 1 < W and M[y][x+1] == '.':
        q.append([x+1, y, depth+1])
        M[y][x+1] = '#'
    if y - 1 >= 0 and M[y-1][x] == '.':
        q.append([x, y-1, depth+1])
        M[y-1][x] = '#'
    if y + 1 < H and M[y+1][x] == '.':
        q.append([x, y+1, depth+1])
        M[y+1][x] = '#'
print(depth)
### BUGGY CODE ###

import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print(s,e_2[j],vs)
                dfs(e_2[j],count,target,vs[0:])

def dijsktra(start, v, e):
    d = [0]*v
    prev = [0]*v
    v_q=[[] for i in range(v)];

    INF = 9999999999999999999
    for u in range(v):
        if(u != start):
            d[u] = INF
        else:
            d[u] = 0 
        prev[u] = -1
        heapq.heappush(v_q[u],d[u])

    

    while(True):
        min = INF
        u = -1
        for i in range(len(v_q)):
            if(len(v_q[i]) != 0):
                if(min > v_q[i][0]):
                    min = v_q[i][0]
                    u = i
        if(u!=-1):
            heapq.heappop(v_q[u])
        if(min == (INF)):
            break
        for j in range(e):
            if(u == e_1[j]):
                alt = d[u]+e_w[j]
                if(d[e_2[j]] > alt):
                    d[e_2[j]] = alt
                    prev[e_2[j]] = u
                    heapq.heappush(v_q[e_2[j]],alt)

    for i in range(v):
        if(d[i] != INF):
            print(d[i])
        else:
            print("INF")

v,e,r=map(int, input().split());

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

dijsktra(r,v,e)



### FIXED CODE ###

import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

for i in range(v):
    if(d[i] != INF):
        print(d[i])
    else:
        print("INF")
### BUGGY CODE ###

from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NX, NY in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PX, PY in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
        [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

ans = 0

for i in range(0, N-1):
    for j in range(i+1, N):
        ans += A[i]*A[j]

div, mod = divmod(ans, 1000000007)

print(mod)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))


sum_a = sum(A)
ans = 0
mod = int(1e9+7)

for a in A:
    sum_a -= a
    ans += (sum_a * a) % mod

ans %= mod
print(int(ans))
### BUGGY CODE ###

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

list_aaa = []

for i in range(M):
    L,R = map(int,input().split())
    aaa = set(range(L,R+1))
    list_aaa.append(aaa)
#print(list_aaa)

and_set = list_aaa[0]

for i in range(M-1):
    and_set = and_set.intersection(list_aaa[i+1])


print(len(and_set))



### FIXED CODE ###

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

L_list = []
R_list = []

for i in range(M):
    L,R = map(int,input().split())
    L_list.append(L)
    R_list.append(R)
L_max = max(L_list)
R_min = min(R_list)

#print(range(L_max,R_min+1))
print(len(range(L_max,R_min+1)))
### BUGGY CODE ###

n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  print(sum(Sev[l:r]))

### FIXED CODE ###

n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

Simos = [0] * n
Simos[0] = Sev[0]
for i in range(1, n):
  Simos[i] = Simos[i-1] + Sev[i]
    
for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  r = r-1
  if l == 0:
    print(Simos[r])
  else:
    print(Simos[r] - Simos[l-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (x+i)+(y+j)*w not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (x+i)+(y+j)*w not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
"""
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
"""
for y in range(h):
    for x in range(w):
        for i in range(-1,2,1):
            for j in range(-1,2,1):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if grid[y][x] != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)
### BUGGY CODE ###

from math import gcd

def euler_phi(n):
    res=n
    for x in range(2,int(n**.5)+2):
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res


def biggcd(n,m):
    g=gcd(n,m)
    res=g
    count=2
    while True:
        test=gcd(g**count,m)
        if test>res:
            res=test
            count+=1
        else:
            break
    return res


def solve(a,m,n):
    #print(a,m,n)
    if gcd(a,m)==1:
        if m==1:
            return 1
        G=gcd(euler_phi(m),m)
        r0=solve(a,G,n)
        return (((pow(a,n*r0)-n*r0)//G)*pow(n*euler_phi(m)//G,euler_phi(m)-1,m)*euler_phi(m)+r0)%(m*euler_phi(m)//G)
    else:
        big=biggcd(a,m)
        k0=solve(a,m//big,n*big)
        return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))
    #ans=solve(A,M,1)
    #print(pow(A,ans,M)%M==ans%M)


### FIXED CODE ###

from math import gcd

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(32000)

def euler_phi(n):
    res=n
    for x in prime:
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res


def biggcd(n,m):
    g=gcd(n,m)
    res=g
    count=2
    while True:
        test=gcd(g**count,m)
        if test>res:
            res=test
            count+=1
        else:
            break
    return res


def solve(a,m,n):
    #print(a,m,n)
    if gcd(a,m)==1:
        if m==1:
            return 1
        phi=euler_phi(m)
        G=gcd(phi,m)
        r0=solve(a,G,n)
        mod=m*phi//G
        return ((((pow(a,n*r0,mod)-n*r0)%mod)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%mod
    else:
        big=biggcd(a,m)
        k0=solve(a,m//big,n*big)
        return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))
    #ans=solve(A,M,1)
    #print(pow(A,ans,M)%M==ans%M)