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

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

No=0
for b in range(2,n+1):
    m=0
    N=n
    while N!=0:
        m+=N%b
        N=N//b
    if m==s:
        print(b)
        No=1
        break
if n==s:
    print(n+1)
    No =1
if No==0:
    print(-1)


### FIXED CODE ###

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

No=0
if n==s:
    print(n+1)
    No =1
else:
    for b in range(2,int(n**0.5)+2):
        m=0
        N=n
        while N!=0:
            m+=N%b
            N=N//b
            if m>s:
                break    
        if m==s:
            print(b)
            No=1
            exit()
    for p in range(int(n**0.5-1),0,-1):
        b = float(n-s)/float(p)+1.0
        if abs(b-int(b))<10**(-10)and b>0:
            b=int(b)
            m=0
            N=n
            while N!=0:
                m+=N%b
                N=N//b
                if m>s:
                    break    
            if m==s:
                print(b)
                No=1
                exit()
if No==0:
    print(-1)
### BUGGY CODE ###

from bisect import bisect_left
from random import randint
D = int(input())
Cs = list(map(int, input().split()))
Sss = []
for _ in range(D):
    Ss = list(map(int, input().split()))
    Sss.append(Ss)

def change(d, afterIdx):
    global score
    i = d - 1
    beforeIdx = Ts[i] - 1
    afterIdx -= 1
    if beforeIdx == afterIdx:
        return

    newScore = score

    before = lasts[beforeIdx]
    # dが何番目にあるか
    k1 = bisect_left(before, d)
    w = before[k1+1] - d
    h = d - before[k1-1]
    newScore -= Sss[i][beforeIdx]
    newScore -= w * h * Cs[beforeIdx]

    after = lasts[afterIdx]
    # dが何番目にあるか
    k2 = bisect_left(after, d)
    w = after[k2] - d
    h = d - after[k2-1]
    newScore += Sss[i][afterIdx]
    newScore += w * h * Cs[afterIdx]

    if newScore > score:
        lasts[beforeIdx].pop(k1)
        lasts[afterIdx].insert(k2, d)
        Ts[i] = afterIdx + 1
        score = newScore

Ts = []
for _ in range(D):
    Ts.append(randint(1, 26))

score = 0
lasts = [[0] for _ in range(26)]
for i, t in enumerate(Ts):
    d = i + 1
    t -= 1
    score += Sss[i][t]
    lasts[t].append(d)
    for j in range(26):
        score -= (d - lasts[j][-1]) * Cs[j]

for i in range(26):
    lasts[i].append(D+1)


for i in range(50000000):
    change(randint(1, D), randint(1, 26))

for t in Ts:
    print(t)


### FIXED CODE ###

from bisect import bisect_left
from random import randint
D = int(input())
Cs = list(map(int, input().split()))
Sss = []
for _ in range(D):
    Ss = list(map(int, input().split()))
    Sss.append(Ss)

def change(d, afterIdx):
    global score
    i = d - 1
    beforeIdx = Ts[i] - 1
    afterIdx -= 1
    if beforeIdx == afterIdx:
        return

    newScore = score

    before = lasts[beforeIdx]
    # dが何番目にあるか
    k1 = bisect_left(before, d)
    w = before[k1+1] - d
    h = d - before[k1-1]
    newScore -= Sss[i][beforeIdx]
    newScore -= w * h * Cs[beforeIdx]

    after = lasts[afterIdx]
    # dが何番目にあるか
    k2 = bisect_left(after, d)
    w = after[k2] - d
    h = d - after[k2-1]
    newScore += Sss[i][afterIdx]
    newScore += w * h * Cs[afterIdx]

    if newScore > score:
        lasts[beforeIdx] = before[:k1] + before[k1+1:]
        lasts[afterIdx] = after[:k2] + [d] + after[k2:]
        Ts[i] = afterIdx + 1
        score = newScore

Ts = []
for _ in range(D):
    Ts.append(randint(1, 26))

score = 0
lasts = [[0] for _ in range(26)]
for i, t in enumerate(Ts):
    d = i + 1
    t -= 1
    score += Sss[i][t]
    lasts[t].append(d)
    for j in range(26):
        score -= (d - lasts[j][-1]) * Cs[j]

for i in range(26):
    lasts[i].append(D+1)


for i in range(100000):
    change(randint(1, D), randint(1, 26))

for t in Ts:
    print(t)
### BUGGY CODE ###

import copy

N = input()
A = input().split()
n = int(N)
Int_A = [int(a) for a in A]


result = [Int_A[0]]
Int_A.remove(Int_A[0])

i = 1


def check(a, other):
    if len(other) == 1:
        if result[0] == other[0] ^ a:
            print("Yes")
            exit()
        return []

    res = []
    co_other = copy.deepcopy(other)
    for o in other:
        c = a ^ o
        co_other.remove(o)
        if c in co_other:
            res.append(o)
        co_other.append(o)

    return res

Int_C = copy.deepcopy(Int_A)

def deep_check(depth):


    resp = check(result[depth - 1], Int_C)

    if len(resp) == 0:
        return

    for k in resp:
        result.append(k)
        Int_C.remove(k)
        depth += 1
        deep_check(depth)
        result.remove(k)
        Int_C.append(k)
    depth -= 1
    return

deep_check(1)
print('No')



### FIXED CODE ###

# import copy
#
N = input()
A = input().split()
n = int(N)
Int_A = [int(a) for a in A]

k = 0

for a in Int_A:
    k ^= a

if k == 0:
    print("Yes")
else:
    print("No")


#
# result = [Int_A[0]]
# Int_A.remove(Int_A[0])
#
#
# def check(a):
#     if len(Int_A) == 1:
#         if result[0] == Int_A[0] ^ a:
#             print("Yes")
#             exit()
#         return []
#
#     res = []
#     co_other = copy.deepcopy(Int_A)
#     for o in Int_A:
#         co_other.remove(o)
#         if a ^ o in co_other:
#             res.append(o)
#         co_other.append(o)
#     del co_other
#
#     return res
#
#
# def deep_check(depth):
#
#     resp = check(result[depth - 1])
#
#     if len(resp) == 0:
#         depth -= 1
#         return
#
#     for k in resp:
#         result.append(k)
#         Int_A.remove(k)
#         depth += 1
#         deep_check(depth)
#         result.remove(k)
#         Int_A.append(k)
#     depth -= 1
#     return
#
#
# deep_check(1)
# print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    """Function."""
    s = str(input())

    total = 0
    for i in range(len(s)):
        if s[i] == "B":
            total += s[i+1:].count("W")

    print(total)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    """Function."""
    s = str(input())

    total = 0
    b_count = 0
    for i in range(len(s)):
        if s[i] == "B":
            b_count += 1
        if s[i] == "W":
            total += b_count

    print(total)


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

n = int(input())
p = list(map(float, input().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]

dp[0][0] = 1
dp[1][1] = p[0]
for i in range(n):
    dp[i + 1][0] = dp[i][0] * (1 - p[i])

for i in range(1, n):
    for j in range(i):
        dp[i + 1][j + 1] = dp[i][j] * p[i] + dp[i][j + 1] * (1 - p[i])
    dp[i + 1][i + 1] = dp[i][i] * p[i]

print(sum(dp[n][(n + 1) // 2:]))


### FIXED CODE ###

n = int(input())
p = list(map(float, input().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]

dp[0][0] = 1
dp[1][1] = p[0]
for i in range(n):
    dp[i + 1][0] = dp[i][0] * (1 - p[i])

for i in range(1, n):
    for j in range(i):
        dp[i + 1][j + 1] = dp[i][j] * p[i] + dp[i][j + 1] * (1 - p[i])
    dp[i + 1][i + 1] = dp[i][i] * p[i]

print(sum(dp[n][(n + 1) // 2:]))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a in As:
        need = num_lis[a-1]
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], int(str(a)+str(dp[i-need])))

print(dp[-1])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], dp[i-need]*10+a)

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

import numpy as np

def rec_z():
    for i in range(N):
        for j in range(a[i],Hmax+1):
            dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = np.full(Hmax+1, INF, dtype=int)
dp[0] = 0
print(rec_z())

### FIXED CODE ###

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())
### BUGGY CODE ###

n=int(input())
P=[int(i) for i in input().split()]
n_max=10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
def bitlb(BIT,s):
  if s<=0:
    return 0
  else:
    ret=0
    k=2**nn
    while k>0:
      if k+ret<=2**nn and BIT[k+ret]<s:
        s-=BIT[k+ret]
        ret+=k
      k//=2
    return ret+1
D=dict()
for i in range(n):
  D[P[i]]=i+1
PP=sorted(P,reverse=True)
bitadd(BIT,D[PP[0]],1)
ans=0
for i in range(1,n):
  cur=D[PP[i]]
  bitadd(BIT,cur,1)
  tot=bitsum(BIT,cur)
  l2,l1,r1,r2=bitlb(BIT,tot-2),bitlb(BIT,tot-1),min(n+1,bitlb(BIT,tot+1)),min(n+1,bitlb(BIT,tot+2))
  add=PP[i]*((-l1+cur)*(r2-r1)+(l1-l2)*(r1-cur))
  ans+=add
print(ans)

### FIXED CODE ###

n=int(input())
P=[int(i) for i in input().split()]
n_max=10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
def bitlb(BIT,s):
  if s<=0:
    return 0
  else:
    ret=0
    k=2**nn
    while k>0:
      if k+ret<=2**nn and BIT[k+ret]<s:
        s-=BIT[k+ret]
        ret+=k
      k//=2
    return ret+1
D=dict()
for i in range(n):
  D[P[i]]=i+1
PP=sorted(P,reverse=True)
bitadd(BIT,D[PP[0]],1)
ans=0
for i in range(1,n):
  cur=D[PP[i]]
  bitadd(BIT,cur,1)
  tot=bitsum(BIT,cur)
  l2,l1,r1,r2=bitlb(BIT,tot-2),bitlb(BIT,tot-1),min(n+1,bitlb(BIT,tot+1)),min(n+1,bitlb(BIT,tot+2))
  add=PP[i]*((-l1+cur)*(r2-r1)+(l1-l2)*(r1-cur))
  ans+=add
print(ans)
### BUGGY CODE ###

K, Q = map(int, input().split())
D = list(map(int, input().split()))
SD = [0]
for i in range(K):
    SD.append(SD[-1] + D[i])

for _ in range(Q):
    n, x, m = map(int, input().split())
    md = [D[i] % m for i in range(K)]
    md0 = md.count(0)
    smd = [0]
    for i in range(K):
        smd.append(smd[-1] + md[i])
    roop = (n - 1) // K
    amari = (n - 1) % K
    an = x + smd[-1] * roop + smd[amari]
    minus = an // m - x // m
    res = n - 1 - minus - md0 * roop - md[:amari].count(0)
    print(res)



### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = [D[i] % m for i in range(K)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N, Q = mi()
# print(N, Q)
S = li()
Alist = []
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = mi()
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        Alist.append(i)
AClist = [0]*(N+1)
for i in range(N - 1):
    if i in Alist:
        AClist[i + 2] = AClist[i+1] + 1
    else:
        AClist[i+2] = AClist[i+1]

# print(AClist)

for i in range(Q):
    if AClist[l[i] - 1] != AClist[l[i]]:
        print(AClist[r[i]] - AClist[l[i]])
    else:
        print(AClist[r[i]] - AClist[l[i]-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N, Q = mi()
# print(N, Q)
S = li()
Alist = []
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        Alist.append(i)
Aset = set(Alist)
AClist = [0]*(N+1)
for i in range(N-1):
    if i in Aset:
        AClist[i + 2] = AClist[i + 1] + 1
    else:
        AClist[i+2] = AClist[i+1]
        # print(AClist)

for i in range(Q):
    l, r = mi()
    if AClist[l - 1] != AClist[l]:
        print(AClist[r] - AClist[l])
    else:
        print(AClist[r] - AClist[l-1])
### BUGGY CODE ###

from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [readline() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
seen = [[False]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-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)]

while len(deq):
  h,w = deq.popleft()
  if seen[h][w]:
    continue
    seen[h][w] = True
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)


### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
### BUGGY CODE ###

import heapq

WALLET_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[WALLET_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX))]
    while q:
        t, loc, silvers = heapq.heappop(q)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], WALLET_MAX)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > WALLET_MAX:
                break
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline

NCOSTS = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0


def node(city, silvers):
    return silvers * N + city


for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for j in range(a, NCOSTS):
        adj[node(u, j)].append((node(v, j - a), b))
        adj[node(v, j)].append((node(u, j - a), b))

for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    for j in range(NCOSTS - c):
        adj[node(i, j)].append((node(i, j + c), d))


mintime = [TIME_MAX for _ in range(N * NCOSTS)]


def search():
    q = [(0, node(0, min(S, NCOSTS - 1)))]
    while q:
        t, node1 = heapq.heappop(q)
        if t > mintime[node1]:
            continue
        for node2, cost in adj[node1]:
            ntime = t + cost
            if mintime[node2] > ntime:
                mintime[node2] = ntime
                heapq.heappush(q, (ntime, node2))


search()
for i in range(1, N):
    print(min(mintime[node(i, j)] for j in range(NCOSTS)))
### BUGGY CODE ###

S = input()

def delete_cube(cube):
    new_cube = []
    cnt = 0
    i=0
    while(i < len(cube)):
        if i == len(cube)-1:
            new_cube.append(cube[i])
            i+=1
        elif (cube[i]=='0' and cube[i+1]=='1') or (cube[i]=='1' and cube[i+1]=='0'):
            cnt+=2
            i+=2
        else:
            new_cube.append(cube[i])
            i+=1
    return(new_cube, cnt)

total_cnt=0
while(True):
    S,cnt = delete_cube(S)
    if cnt==0:
        break
    total_cnt+=cnt
print(total_cnt)


### FIXED CODE ###

S = input()

cnt1=0
cnt0=0
for i in range(len(S)):
    if S[i]=='0':
        cnt0+=1
    elif S[i]=='1':
        cnt1+=1
if cnt1 == 0 or cnt0 == 0:
    print(0)
else:
    if cnt1>cnt0:
        print(cnt0*2)
    else:
        print(cnt1*2)
### BUGGY CODE ###

n = int(input())
s = input()
sr = s[::-1]

if s == "." * n or s == "#" * n:
    print(0)
else:
    ans = n
    for i in range(n):
        num = s[:i].count("#") + s[i:].count(".")
        ans = min(num, ans)
    print(ans)

### FIXED CODE ###

n = int(input())
s = input()
sr = s[::-1]

ans = s.count(".")
num = ans
for i in range(n):
    if s[i] == ".":
        num -= 1
    else:
        num += 1
    ans = min(num, ans)
print(ans)
### BUGGY CODE ###

H,W=map(int,input().split())
S=[[0 for i in range(0,W)] for i in range(0,H)]
for i in range(0,H):
    S[i]=input().split()

load=[]
for i in range(0,H):
    for j in range(0,W):
        if S[i][0][j]=='.':
            load.append((i,j))

ans=0
for i,j in load:
    start=(i,j)
    dp=[[500 for i in range(0,W)] for i in range(0,H)]
    dp[i][j]=0
    q=[]
    q.append((i,j))
    sub=[]
    while q!=[]:
        while q!=[]:
            x=q[0]
            q.remove(x)
            s=x[0]
            t=x[1]
            if (s+1,t) in load and dp[s+1][t]>dp[s][t]+1:
                sub.append((s+1,t))
                dp[s+1][t]=dp[s][t]+1
            if (s,t+1) in load and dp[s][t+1]>dp[s][t]+1:
                sub.append((s,t+1))
                dp[s][t+1]=dp[s][t]+1
            if (s-1,t) in load and dp[s-1][t]>dp[s][t]+1:
                sub.append((s-1,t))
                dp[s-1][t]=dp[s][t]+1
            if (s,t-1) in load and dp[s][t-1]>dp[s][t]+1:
                sub.append((s,t-1))
                dp[s][t-1]=dp[s][t]+1
            if q==[]:
                q=sub
                sub=[]
                break
    test=max(dp[i][j] for i in range(0,H) for j in range(0,W) if (i,j) in load)
    if test>ans:
        ans=test
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[[0 for i in range(0,W)] for i in range(0,H)]
for i in range(0,H):
    S[i]=input().split()

load=[]
for i in range(0,H):
    for j in range(0,W):
        if S[i][0][j]=='.':
            load.append((i,j))

ans=0
for i,j in load:
    start=(i,j)
    dp=[[500 for i in range(0,W)] for i in range(0,H)]
    dp[i][j]=0
    q=[]
    q.append((i,j))
    sub=[]
    while q!=[]:
        while q!=[]:
            x=q[0]
            q.remove(x)
            s=x[0]
            t=x[1]
            if (s+1,t) in load and dp[s+1][t]>dp[s][t]+1:
                sub.append((s+1,t))
                dp[s+1][t]=dp[s][t]+1
            if (s,t+1) in load and dp[s][t+1]>dp[s][t]+1:
                sub.append((s,t+1))
                dp[s][t+1]=dp[s][t]+1
            if (s-1,t) in load and dp[s-1][t]>dp[s][t]+1:
                sub.append((s-1,t))
                dp[s-1][t]=dp[s][t]+1
            if (s,t-1) in load and dp[s][t-1]>dp[s][t]+1:
                sub.append((s,t-1))
                dp[s][t-1]=dp[s][t]+1
            if q==[]:
                q=sub
                sub=[]
                break
    test=max(dp[i][j] for i in range(0,H) for j in range(0,W) if (i,j) in load)
    if test>ans:
        ans=test
print(ans)
### BUGGY CODE ###

def STR(): return input()

mod = 1000000007

s = STR()
l = len(s)
dp = [[0] * 13 for _ in range(l + 1)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
dp[0][0] = 1

for i in range(l + 1): #i桁目まで決める
    if s[i-1] == '?':
        for j in range(13): #i-1桁目のあまりがj
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): #i桁目の値
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): #i-1桁目のあまりがj
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
#print(dp)
print(dp[l][5])


### FIXED CODE ###

def STR(): return input()

mod = 1000000007

s = STR()
l = len(s)
dp = [[0] * 13 for _ in range(l + 1)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
dp[0][0] = 1


for i in range(l + 1): #i桁目まで決める
    if s[i-1] == '?':
        for j in range(13): #i-1桁目のあまりがj
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): #i桁目の値
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): #i-1桁目のあまりがj
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
#print(dp)
print(dp[l][5])