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

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().strip().split())
  c_h, c_w = map(int, input().strip().split())
  d_h, d_w = map(int, input().strip().split())
  maze = [list(input().strip()) for _ in range(h)]
  visited = [[0] * w for _ in range(h)]
  
  def bfs():
    dq = deque([(c_h-1, c_w-1, 0)])
    while dq:
      (ih, iw, cnt) = dq.pop()
      if visited[ih][iw]:
        continue
      visited[ih][iw] = 1
      
      if ih == d_h-1 and iw == d_w-1:
        return cnt
      
      for dh in range(-2, 3):
        for dw in range(-2, 3):
          if not (0 <= ih + dh < h and 0 <= iw + dw < w) \
             or visited[ih + dh][iw + dw] == 1 \
             or maze[ih + dh][iw + dw] == '#':
            continue
          if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dq.append((ih + dh, iw + dw, cnt))
          else:
            dq.appendleft((ih + dh, iw + dw, cnt+1))
      
    return -1
  print(bfs())
  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().strip().split())
  c_h, c_w = map(int, input().strip().split())
  d_h, d_w = map(int, input().strip().split())
  maze = [list(input().strip()) for _ in range(h)]
  visited = [[0] * w for _ in range(h)]
  
  def bfs():
    dq = deque([(c_h-1, c_w-1, 0)])
    while dq:
      (ih, iw, cnt) = dq.pop()
      if visited[ih][iw]:
        continue
      visited[ih][iw] = 1
      
      if ih == d_h-1 and iw == d_w-1:
        return cnt
      
      for dh in range(-2, 3):
        for dw in range(-2, 3):
          if not (0 <= ih + dh < h and 0 <= iw + dw < w) \
             or visited[ih + dh][iw + dw] == 1 \
             or maze[ih + dh][iw + dw] == '#':
            continue
          if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dq.append((ih + dh, iw + dw, cnt))
          else:
            dq.appendleft((ih + dh, iw + dw, cnt+1))
      
    return -1
  print(bfs())
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np


N = [int(i) for i in input().split()][0]
array = np.zeros([N, 26])
string = list(input())
strs = []
a0 = ord("a")
for n, s in enumerate(string):
  i = ord(s) - a0
  array[n, i] = 1
  strs.append(i)
qumsum = np.cumsum(array, axis=0)

Q = [int(i) for i in input().split()][0]
queries =[[i for i in input().split()] for _ in range(Q)]

changed = []
for que in queries:
  type_, pos, st = que
  if type_ == "1":
    p = int(pos) - 1
    s1 = strs[p]
    array[p, s1] = 0
    s2 = ord(st) - a0
    strs[p] = s2
    array[p, s2] = 1
    changed.append((p, s1, s2))
  else:
    lq = int(pos) - 1
    rq = int(st)
    sums = qumsum[rq-1, :] - qumsum[lq, :] + array[lq, :]
    for change in changed:
      p, s1, s2 = change
      if lq <= p < rq:
        sums[s1] -= 1
        sums[s2] += 1
    print(np.sum(sums>0))



### FIXED CODE ###



N = [int(i) for i in input().split()][0]
string = list(input())
Q = [int(i) for i in input().split()][0]
queries = [[i for i in input().split()] for _ in range(Q)]

tmp = N 
c = 0
while tmp > 0:
  c += 1
  tmp //= 2
N2 = 2**c
offset = N2 - 1

seg_tree = [0 for _ in range(N2*2 -1)]
for n in range(N):
  ind = ord(string[n]) - ord("a")
  seg_tree[offset + n] = 1 << ind

def set_seg_tree(i, seg_trees):
  if i >= N2 -1:
    return seg_trees[i]
  left = 2*i + 1
  right = 2*i + 2
  l_seg = set_seg_tree(left, seg_trees)
  r_seg = set_seg_tree(right, seg_trees)
  seg_trees[i] = l_seg | r_seg
  return seg_trees[i]
set_seg_tree(0, seg_tree)
    
def update(i, c, seg_trees):
  i += offset
  seg_trees[i] = 1 << c
  while i > 0:
    i = (i - 1)//2
    seg_trees[i] = seg_trees[i * 2 + 1] | seg_trees[i * 2 + 2]

def get_sum(a, b, k, l, r, seg_trees):
  if (b <= l) or (r <= a):
    return 0
  if (a <= l) and (r <= b):
    return seg_trees[k]
  vl = get_sum(a, b, k * 2 + 1, l, (l + r)//2, seg_trees)
  vr = get_sum(a, b, k * 2 + 2, (l + r)//2, r, seg_trees)
  return vl | vr

for query in queries:
  type_, i, q = query
  if type_ == "1":
    i = int(i) - 1
    pos = ord(q) - ord("a")
    update(i, pos, seg_tree)
  else:
    l = int(i) - 1
    r = int(q)
    ret = get_sum(l, r, 0, 0, N2, seg_tree)
    print(bin(ret).count("1"))
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(max(s - 2 * k, 0), k + 1):
    for y in range(k + 1):
        if s - x - y > k:
            continue
        elif s - x - y < 0:
            continue
        z = s - x - y
        if 0 <= z <= k:
            cnt += 1
print(cnt)


### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(max(s - 2 * k, 0), k + 1):
    for y in range(max(s - x - k, 0), min(s - x + 1, k + 1)):
        z = s - x - y
        if 0 <= z <= k:
            cnt += 1
        else:
            continue
print(cnt)
### BUGGY CODE ###

n = int(input())
left = 0
right = n - 1
print(left)
first = input()
second = 'Male' if s_l == 'Female' else 'Male'
p = 0
while True:
    p = (left + right) // 2
    print(p)
    status = input()
    if status == 'Vacant':
        exit()
    if p % 2 == 0:
        if status == first:
            left = p + 1
        else:
            right = p
    else:
        if status == second:
            left = p + 1
        else:
            right = p

### FIXED CODE ###

n = int(input())
left = 0
right = n - 1
print(left)
first = input()
second = 'Male' if first == 'Female' else 'Female'
p = 0
while True:
    p = (left + right) // 2
    print(p)
    status = input()
    if status == 'Vacant':
        break
    if p % 2 == 0:
        if status == first:
            left = p + 1
        else:
            right = p
    else:
        if status == second:
            left = p + 1
        else:
            right = p
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

for i in range(N-1):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

for i in range(N-1):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N-1])
### BUGGY CODE ###

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

def otosidama(N,Y):
    for y in range(N+1,-1,-1):
        if y*10000 > Y:
            continue
        for i in range(N+1-y):
            if (N-y-i)*1000 > Y-y*10000:
                break
            elif i*5000 > Y-y*10000:
                continue
            for h in range(N+1-y-i,-1,-1):
                if y*10000 + i*5000 + h*1000 == Y and y + i + h == N:
                    return y,i,h
    
    return -1,-1,-1

if Y > N*10000:
    print(-1,-1,-1)
else:
    y,i,h = otosidama(N,Y)
    print(y,i,h)

### FIXED CODE ###

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

def otosidama(N,Y):
    for y in range(N+1,-1,-1):
        if y*10000 > Y:
            continue
        for i in range(N+1-y):
            if (N-y-i)*1000 > Y-y*10000:
                break
            else:
                if y*10000 + i*5000 + (N-y-i)*1000 == Y:
                    return y,i,N-y-i
    
    return -1,-1,-1

if Y > N*10000:
    print(-1,-1,-1)
else:
    y,i,h = otosidama(N,Y)
    print(y,i,h)
### BUGGY CODE ###

k = int(input())
queue = [i for i in range(1, 10)]

for i in range(k-1):
  tmp = queue.pop(0)
  r = tmp % 10
  if r != 0:
    queue.append(10*tmp + r -1)
  queue.append(10*tmp + r)
  if r != 9:
    queue.append(10*tmp + r + 1)
print(queue.pop(0))
  

### FIXED CODE ###

from collections import deque
k = int(input())
q = deque([i for i in range(1, 10)])

for i in range(k-1):
  tmp = q.popleft()
  r = tmp % 10
  if r != 0:
    q.append(10*tmp + r -1)
  q.append(10*tmp + r)
  if r != 9:
    q.append(10*tmp + r + 1)
print(q.popleft())
### BUGGY CODE ###

s = input()
K = int(input())

se = set()
for i in range(1,len(s)+1):
	for j in range(len(s)-i+1):
		se.add(s[j:j+i])
print(sorted(list(se))[K-1])

### FIXED CODE ###

s = input()
K = int(input())

se = set()
for i in range(1,min(len(s)+1,K+1)):
	for j in range(len(s)-i+1):
		se.add(s[j:j+i])
print(sorted(list(se))[K-1])
### BUGGY CODE ###

S = list(input())
for q in range(int(input())):
    T = input().rstrip().split()
    if T[0] == "1":
        S = S[::-1]
    else:
        F,C = T[1],T[2]
        if F == "1":
            S = [C] + S
        else:
            S += [C]
print("".join(S))

### FIXED CODE ###

B = input()
order = True
F = ""
for q in range(int(input())):
    T = input().rstrip().split()
    if T[0] == "1":
        order ^= True
    else:
        f,c = T[1],T[2]
        if not((f == "1") ^ order):
            F += c
        else:
            B += c
    #print(F,B)
F = F[::-1]+B
if not order:
    F = F[::-1]
print(F)
### BUGGY CODE ###

import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

G=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
for _ in range(M):
	u,v = map(int, input().split())
	G[u].append(v)

S, T = map(int, input().split())

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# グラフGから、3つ先の到達点のグラフXを作る
X=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

for i in range(N+1):
	g = G[i]

	for g1 in g:
		for g2 in G[g1]:
			for g3 in G[g2]:
#				if (not g3 in X[i]):
#					X[i].append(g3)
				X[i].append(g3)

#p("X",X)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[-1 for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
V[S]=0

# キューに行き先候補を入れて、
from collections import deque

Q = deque()
Q.append(S)

while Q:
	fm = Q.popleft()
#	p("fm, X[fm], Q ", fm, X[fm], Q)
	
	for to in X[fm]:
#		p("  to, V[to], Q ",to, V[to], Q)
		
		b = (V[to]==-1)							# 未訪問である
		#b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to] = V[fm]+1		# 訪問ステップ数の記録
			Q.append(to)			# 次の訪問先として、キューに追加

#	p("V ",V)

#ans = V[T] if V[T]>0 else -1
#print(ans)

print(V[T])


### FIXED CODE ###

import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

G=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
for _ in range(M):
	u,v = map(int, input().split())
	G[u].append(v)

S, T = map(int, input().split())

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[ [-1,-1,-1] for _ in range(N+1) ]			#=> [ [-1,-1,-1], [-1,-1,-1], ... [-1,-1,-1] ]
V[S][0]=0

# キューに行き先候補を入れて、
from collections import deque
Q = deque()
Q.append([S,0])

while Q:
	FM = Q.popleft()
	
	fm = FM[0]
	l =  FM[1]
	
	for to in G[fm]:
		nl = (l+1)%3
		b = (V[to][nl]==-1)							# 未訪問である
		#b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to][nl] = V[fm][l]+1		# 訪問ステップ数の記録
			Q.append([to,nl])			# 次の訪問先として、キューに追加

ans = V[T][0]
if ans > -1: ans //= 3
print(ans)
### BUGGY CODE ###

import sys
L,R=map(int,input().split())
if R-L>2019:
    print(0)
    sys.exit()
c1=R-L
for i in range(L,R+1):
    if i%2019==0:
        print(0)
        sys.exit()
    if c1>2 and i%673==0:
        print(0)
        sys.exit

ls1=[]
for i in range(L,R+1):
    ls1.append(i%2019)
    m=2018
    for i in range(len(ls1)-1):
        for j in range(i+1,len(ls1)):
            m1=(ls1[i]*ls1[j])%2019
            m=min([m1,m])
print(m)


    

### FIXED CODE ###

L,R = map(int,input().split())
r = 2019
if R//2019 != L//2019:
    print(0)
else:
    Rmod = R%2019
    Lmod = L%2019
    for i in range(Lmod,Rmod+1):
        for j in range(i+1,Rmod+1):
            r = min(r,(i*j)%2019)
    print(r)
### BUGGY CODE ###

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

cnt = 1
after = []
for i in range(1, N):
    after.append(P[i-1])
    for a in after:
        if a < P[i]:
            break
    else:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 1
mini = P[0]
for i in range(1, N):
    if P[i] <= mini:
        mini = P[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            if l[k] < l[i] + l[j]:
                count += 1
            else:
                break
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        itr = bisect.bisect_left(l, l[i] + l[j])
        count += itr - 1 - j
print(count)
### BUGGY CODE ###

n = int(input())
s = input()

ans = []
for x in range(len(s)-2):
  for y in range(x+1, len(s)-1):
    for z in range(y+1, len(s)):
      ans.append(s[x]+s[y]+s[z])
print(len(list(set(ans))))

### FIXED CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(1000):
  x = str(i).zfill(3)
  a = s.find(x[0])
  b = s[a+1:].find(x[1])
  c = s[a+b+2:].find(x[2])
  if -1 not in (a,b,c):
    cnt += 1
print(cnt)
### BUGGY CODE ###

import numpy as np

n, w = map(int ,input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)
dp = np.zeros((n+1, w+1))

for i in range(1, n+1):
    weight = items[i-1][0]
    for j in range(0, w+1):
        if j >= weight:
            dp[i][j] = max((dp[i - 1][j - weight] + items[i - 1][1]), dp[i - 1][j])
        else:
            dp[i][j] = dp[i-1][j]


print(int(dp[i][j]))



### FIXED CODE ###

n, w = map(int ,input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)
# dp = np.zeros((n+1, w+1))
dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(1, n+1):
    weight = items[i-1][0]
    for j in range(0, w+1):
        if j >= weight:
            dp[i][j] = max((dp[i - 1][j - weight] + items[i - 1][1]), dp[i - 1][j])
        else:
            dp[i][j] = dp[i-1][j]


print(int(dp[i][j]))
### BUGGY CODE ###

S = list(map(int, list(input())))
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
for i in range(N):
    base = pow(10 % 2019, N-i)
    num = num * 10 + S[i]
    CNT[(num*base)%2019] += 1
ans = 0 
for cnt in CNT:
    if cnt==0: continue
    ans += (cnt*(cnt - 1)) // 2
print(ans)

### FIXED CODE ###

S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)
### BUGGY CODE ###

from collections import deque

h,w = map(int, input().split())
# 場外を追加
A = [['*']*(w+2)] + [['*']+[s for s in input()]+['*'] for _ in range(h)] + [['*']*(w+2)]
visited = [[0]*(w+2) for _ in range(h+2)]

dq = deque()
n=0
directions = [[0,1],[1,0],[0,-1],[-1,0]]
# 初期配置の黒をキューに追加
for hi in range(1,h+1):
    for wi in range(1,w+1):
        if A[hi][wi] == '#':
            dq.append([hi,wi,n])

# キューが空になるまで
while dq:
    hi,wi,n = dq.popleft()
    visited[hi][wi] = 1

    for d in directions:
        new_hi, new_wi = hi+d[0],wi + d[1]
        # 「黒くしてない白マス」をキューに追加
        if visited[new_hi][new_wi] == 0 and A[new_hi][new_wi] == '.':
            dq.append([new_hi,new_wi,n+1])

print(n)

### FIXED CODE ###

from collections import deque

h,w = map(int, input().split())
A = [[s for s in input()] for _ in range(h)]

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        nhi, nwi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if nhi<0 or nhi>=h or nwi<0 or nwi>=w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[nhi][nwi] == -1 and A[nhi][nwi] == '.':
            dq.append([nhi,nwi])
            visited[nhi][nwi] = visited[hi][wi] + 1

ans = -1
for x in visited:
    ans = max(ans,max(x))
print(ans)
### BUGGY CODE ###

n = int(input())
xs = list(map(int, input().split()))

ans = 0
sums = 0
xors = 0
for i in range(n):
  for j in range(i, n):
    sums += xs[j]
    xors ^= xs[j]
    if sums == xors:
      ans += 1
  sums = 0
  xors = 0
print(ans)

### FIXED CODE ###

n = int(input())
xs = list(map(int, input().split()))
 
ans = 0
sums = xs[0]
xors = xs[0]
i, j = 0, 0

while True:
  if xors == sums:
    ans += j - i + 1
    j += 1
    if j >= n: break
    sums += xs[j]
    xors ^= xs[j]
  else:
    sums -= xs[i]
    xors ^= xs[i]
    i += 1
    
print(ans)
### BUGGY CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)




### FIXED CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)
### BUGGY CODE ###

N, M = map(int,input().split())
AB = []
for _ in range(M):
    a,b = map(int,input().split())
    if  a == 1 or b== N:
        AB.append((a,b))
AB = set(AB)
for ab in AB:
    if ab[0] == 1:
        for  cd in AB:
            if cd[1] == N and ab[1] == cd[0]:
                    print("POSSIBLE")
                    exit()
print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int,input().split())
AB = []
for _ in range(M):
    a,b = map(int,input().split())
    if  a == 1 or b== N:
        AB.append((a,b))
set1 = set()
set2 = set()
for ab in AB:
    if ab[0] == 1:
        set1.add(ab[1])
    if ab[1] == N:
        set2.add(ab[0])
if set1 & set2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import itertools

N = int(input())
L = [int(i) for i in input().split()]


def solve():
    pattern_cnt = 0

    for pattern in list(itertools.combinations(L, 3)):
        if (pattern[0] < pattern[1] + pattern[2]) and (pattern[2] < pattern[0] + pattern[1]) and  (pattern[1] < pattern[0] + pattern[2]):
            pattern_cnt += 1

    return pattern_cnt


print(solve())


### FIXED CODE ###

import bisect


def resolve():
    n = int(input())
    li = list(map(int, input().split()))
    ans = 0

    li.sort()

    for i in range(n):
        for j in range(i + 1, n):
            cnt = bisect.bisect_left(li, li[i] + li[j])

            ans += cnt - j - 1

    print(ans)

resolve()
### BUGGY CODE ###

from math import gcd
import sys
input = sys.stdin.readline

def lcm(a, b):
    return a*b//gcd(a,b)


# Load data
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
# LCM: dict 最小公倍数の素因数分解
LCM = 1
for a in A:
    LCM = lcm(LCM, a)
# A2Factor: list A[i]の素因数分解
A2Factor = []

ans = 0
for a in A:
    ans += (LCM//a)%mod
    ans %= mod

print(ans % mod)


### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
### BUGGY CODE ###

s=[""]*2
s[1]=input()
q=int(input())
s[0]=""
f=1
for i in range(q):
  a=list(input().split())
  #print(i,a,s)
  if int(a[0])==1:
    f=(f+1)%2
  else:
    s[(f+int(a[1]))%2]+=a[2]
    
if f==1:
  print(s[0][::-1]+s[1])
else:
  print(s[1][::-1]+s[0])
  

### FIXED CODE ###

s1=list(input())
q=int(input())
s0=[]
f=1
for i in range(q):
  a=list(input().split())
  #print(i,a,s)
  if int(a[0])==1:
    f=(f+1)%2
  else:
    if (f+int(a[1]))%2==0:
      s0.append(a[2])
    else:
      s1.append(a[2])
if f==1:
  print("".join(s0[::-1])+"".join(s1))
else:
  print("".join(s1[::-1])+"".join(s0))
### BUGGY CODE ###

def sol():
    h,w=map(int,input().split())
    d=[]
    for i in range(h):
        s=input()
        d.append(s)
    x=h*w
    p=[[x+1]*x for i in range(x)]
    for i in range(x):
        for j in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            if "."==d[ih][iw]==d[jh][jw] and ih==jh and abs(iw-jw)==1:
                p[i][j]=1
                p[j][i]=1
            if "."==d[ih][iw]==d[jh][jw] and iw==jw and abs(ih-jh)==1:
                p[i][j]=1
                p[j][i]=1
            if i==j:
                p[i][j]=0
    for i in range(x):
        ih,iw=i//w,i%w
        if d[ih][iw]!=".": continue
        for j in range(x):
            jh,jw=j//w,j%w
            if d[jh][jw]!=".": continue
            for k in range(x):
                ih,iw=i//w,i%w
                jh,jw=j//w,j%w
                kh,kw=k//w,k%w
                if d[ih][iw]==d[jh][jw]==d[kh][kw]==".":
                    p[j][k]=min(p[j][k],p[j][i]+p[i][k])
    ans=0
    for i in p:
        for j in i:
            if j<x+1:
                ans=max(ans,j)
    print(ans)

if __name__=="__main__":
    sol()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
def sol():
    h,w=map(int,input().split())
    d=[]
    for i in range(h):
        s=input()
        d.append(s)
    x=h*w
    p=[[x+1]*x for i in range(x)]
    for i in range(x):
        for j in range(i+1):
            if i==j:
                p[i][j]=0
                p[j][i]=0
            ih,iw,jh,jw=i//w,i%w,j//w,j%w
            if d[ih][iw]==d[jh][jw]=="." and ih==jh and abs(iw-jw)==1:
                p[i][j]=1
                p[j][i]=1
            if d[ih][iw]==d[jh][jw]=="." and iw==jw and abs(ih-jh)==1:
                p[i][j]=1
                p[j][i]=1


    for i in range(x):
        ih,iw=i//w,i%w
        if d[ih][iw]!=".": continue
        for j in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            if d[jh][jw]!=".": continue
            for k in range(j+1):
                ih,iw=i//w,i%w
                jh,jw=j//w,j%w
                kh,kw=k//w,k%w
                if d[kh][kw]==".":
                    p[j][k]=min(p[j][k],p[j][i]+p[i][k])
                    p[k][j]=min(p[k][j],p[j][i]+p[i][k])
    ans=0
    for i in p:
        for j in i:
            if j<x+1:
                ans=max(ans,j)
    print(ans)

if __name__=="__main__":
    sol()