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

t=input()
check=False
res=0
l=len(t)
res=""
for i in range(len(t)):
  if t[i]=="?":
      res+="D"
  else:res+=t[i]
print(res)
  

### FIXED CODE ###

t=input()
check=False
print(t.replace('?', 'D'))
### BUGGY CODE ###

n = int(input())
 
dx =[0, 1]
 
l = [0]
i = 0
 
while(n not in l):
    i += 1
    l = list(set(l))
    for j in range(len(l)):
        a = l[0]
        l.remove(l[0])
        for k in range(2):
            l.append(a + dx[k]*i)
 
 
print(i)


### FIXED CODE ###

import math
n = int(input())
print(math.ceil((-1+(1+8*n)**(1/2))/2))
### BUGGY CODE ###

# -*- coding:utf-8 -*-
S = list(input())

loop_idx = 0
loop_len = -(-len(S)//2)
cnt = 0

if len(S) == 1:
    pass
else:
    while loop_idx < loop_len:
        if S[0] == "W":
            S.pop(0)
        if S[-1] == "B":
            S.pop(-1)
        for i in range(len(S)-1,0,-1):
            if S[i]=="W" and S[i-1] == "B":
                cnt += 1
                S[i],S[i-1] = "B","W"
        loop_idx += 1
print(cnt)

### FIXED CODE ###

# -*- coding:utf-8 -*-
S = list(input())

cnt_b = 0 
ans = 0

for i in range(len(S)):
    if S[i] == "B":
        cnt_b += 1
    if S[i] == "W":
        ans += cnt_b
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    A,B=map(int, input().split())
    gcd_ab = gcd(A,B)
    ans={1}
    i = 2
    while i <= gcd_ab:
        if gcd_ab % i == 0:
            ans.add(i)
            gcd_ab //= i
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    A,B=map(int, input().split())
    ans = factorization(gcd(A,B))
    if ans[0][0] == 1:
        print(1)
    else:
        print(len(ans)+1)

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

n=int(input())
l = list(map(int,input().strip().split()))[:n] 
rs= 1
for i in range(n):
    rs=l[i]*rs
    if rs>10**18:
        rs = -1
print(rs)

### FIXED CODE ###

n=int(input())
l = list(map(int,input().strip().split()))[:n] 
rs= 1
l.sort()
if l[0]==0 :
    rs=0
else:
    for i in range(n):
        if(10**18 // rs < l[i]):
            rs = -1
            break
        rs=l[i]*rs
print(rs)
### BUGGY CODE ###

moji=input()
cycle=int(input())
for i in range(cycle):
  line=input()
  if line[0]=="1":
    moji=moji[::-1]
  elif line[0]=="2":
    fi,ci=line[2],line[4]
    if fi=="1":
      moji=ci+moji
    elif fi=="2":
      moji=moji+ci
print(moji)

### FIXED CODE ###

def main():
    moji=input()
    cycle=int(input())
    flont_or_back=0
    flont=""
    back=""
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    flont=ci+flont
                else:
                    back+=ci
            else:
                if fi=="1":
                    back+=ci
                else:
                    flont=ci+flont
    moji=flont+moji+back
    if flont_or_back%2==0:
        print(moji)
    else:
        print(moji[::-1])
    

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

def bell(edges, n):
    count = 0
    dist = [-10000000000000000 for i in range(n)]
    dist[0] = 0

    changed = True

    while changed:
        count  += 1
        if count == 1000000:
            print('inf')
            exit()
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                changed = True
            dist[edge[1]] = max(dist[edge[0]] + edge[2], dist[edge[1]])
                
    return dist


n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b, c = (int(x) for x in input().split())
    edges.append([a-1, b-1, c])

res = bell(edges, n)

print(res[n-1])

### FIXED CODE ###

N, M = map(int, input().split())
Edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    c = -c
    Edges.append([a, b, c])
 
dist = [float('inf')] * N
dist[0] = 0
 
for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()
 
print(-dist[-1])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

# 区間DP
# dp[l][r] = 区間[l,r]のスライムを合体するときの最小コスト
# dp[l][r] = min(dp[l][m] + dp[m + 1][r]) + sum(l,r)

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

A = [0] + A
for i in range(1,len(A)):
  A[i] += A[i - 1]

INF = 10 ** 10
dp = [[INF] * N for i in range(N)]
for i in range(N):
  dp[i][i] = 0

# 区間の長さが小さい順にループする(1～N)
for i in range(N): # 区間の長さ
  for l in range(N - i):
    r = l + i
    # lからrまでの区間で最小となるdp[l][m] + dp[m][r]の組み合わせを探す
    # lからrまでのAの累積和
    cums = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cums < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cums
        
print(dp[0][-1])

### FIXED CODE ###

import sys
readline = sys.stdin.readline

# 区間DP
# dp[l][r] = 区間[l,r]のスライムを合体するときの最小コスト
# dp[l][r] = min(dp[l][m] + dp[m + 1][r]) + sum(l,r)

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

A = [0] + A
for i in range(1,len(A)):
  A[i] += A[i - 1]

INF = 10 ** 18
dp = [[INF] * N for i in range(N)]
for i in range(N):
  dp[i][i] = 0

# 区間の長さが小さい順にループする(1～N)
for i in range(N): # 区間の長さ
  for l in range(N - i):
    r = l + i
    # lからrまでの区間で最小となるdp[l][m] + dp[m][r]の組み合わせを探す
    # lからrまでのAの累積和
    cums = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cums < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cums
        
print(dp[0][-1])
### BUGGY CODE ###

s1=input()
s2=input()
n=len(s1)
m=len(s2)
# import numpy as np
dp=[["" for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+s1[i-1]
        else:
            a=dp[i-1][j]
            b=dp[i][j-1]
            if len(a)>len(b):
                dp[i][j]=a
            else:
                dp[i][j]=b
# print(np.array(dp))
print(dp[-1][-1])

### FIXED CODE ###

s1=input()
s2=input()
n=len(s1)
m=len(s2)
# import numpy as np
dp=[[0 for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# print(np.array(dp))
ans=""
# print(dp[-1][-1])
i=n
j=m
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=s1[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

#import numpy as np

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

prices = list(map(int, input().split(" ")))
for i in range(M):
    max_p = max(prices) 
    max_i = prices.index(max_p)
    prices[max_i] //=  2 

out = sum(prices)
print(out)

### FIXED CODE ###

from heapq import heappush, heappop

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

prices = []
for price in map(int, input().split(" ")):
    heappush(prices, -price)


for i in range(M):
    max_p = - (heappop(prices))
    half_p = max_p // 2
    heappush(prices, - half_p)

out = - sum(prices)
print(out)
### BUGGY CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
for i,m in p.items():
  if(m == max(p.values())):
    keys.append(i)
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])

### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)
 
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
u = max(p.values())
for i,m in res:
  if(m == u):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, parent):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    if not ki[i][0]:
        return
    for j in ki[i][0]:
        if j == parent:
            continue
        dfs(j, num_tmp, i)
    return

for i in range(N-1):
    a, b = map(int, input().split())
    ki[a-1][0].append(b-1)
    ki[b-1][0].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    ki[p-1][1] += x

dfs(0, 0, -1)
print(*result)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n,q=[int(_) for _ in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n
 
def dfs(numQ,parent):
    for child in ki[numQ]:
        if child==parent:
            continue
        ans[child]+=ans[numQ]
        dfs(child,numQ)
 
for i in range(n-1):
    a,b=[int(_) for _ in input().split()]
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
 
for i in range(q):
    p,x=[int(_) for _ in input().split()]
    ans[p-1]+=x
 
dfs(0,-1)
print(*ans)
### BUGGY CODE ###

n = int(input())

answer = sum([i for i in range(n)])

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline

a = int(input())

print(int((a-1)*(a)//2))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
  def __init__(self, n):
    self.n = n
    # n+1なのはノード番号とリストのインデックスを一致させるため
    # root[x]<0ならそのノードが根かつその絶対値が木の要素数
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  
  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
    
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1
 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
  
n, k, l = map(int, input().split())
UFd= UnionFind(n)
UFt= UnionFind(n)

for i in range(k):
  p, q = map(int, input().split())
  UFd.Unite(p, q)

for j in range(l):
  p, q = map(int, input().split())
  UFt.Unite(p, q)
  
ids = []
d = {}
for i in range(n):
  if UFd.root[i+1] > 0:
    idd = UFd.root[i+1]
  else:
    idd = i+1
  if UFt.root[i+1] > 0:
    idt = UFt.root[i+1]
  else:
    idt = i+1
  iddt = idd*10**6+idt
  ids.append(iddt)
  if iddt in d:
    d[iddt] += 1
  else:
    d[iddt] = 1
ans = ''
for i in range(n):
  if i != 0:
    ans += ' '
  ans += str(d[ids[i]])
print(ans)    

### FIXED CODE ###

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

ans = ''
for j_ in range(n):
  if j_ != 0:
    ans += ' '
  ans += str(d[IDs[j_]])
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
V,C = zip(*CA.most_common())
S = 0
for i in range(len(C)):
    L = C[i]
    if L == 1:
        break
    S += int(L*(L-1)/2)
for k in range(N):
    print(S - A.count(A[k]) + 1)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in CA.values():
    S += i*(i-1)//2
for x in A:
    print(S - CA[x] + 1)
### BUGGY CODE ###

N,A,B=map(int,input().split())
L=[]
i=0
while i < N:
    for j in range(A-1):
        L.append("b")
        i=i+1
        if i>N:
            break
    for k in range(B-1):
        L.append("r")
        i=i+1
        if i>N:
            break
print(L.count("b"))

### FIXED CODE ###

N,A,B=map(int,input().split())
C=A+B
D=N//C
count=D*A
N=N-C*D
while N>0:
    N=N-A
    if N>0:
        count=count+A
    elif N<=0:
        count=count+(A+N)
        break
    N=N-B
    if N<=0:
        break
    else:
        pass
print(count)
### BUGGY CODE ###

N,K = map(int, input().split())
S = input()

a = []
b = []
before_num = '0'
count = 0
for i in range(N):
  if before_num==S[i]:
    count+=1
  else:
    if before_num=='0':
      a.append(count)
    else:
      b.append(count)
    before_num = S[i]
    count = 1
  if i==N-1:
    if before_num=='0':
      a.append(count)
    else:
      b.append(count)
b += [0]

if len(a)<=K:
  print(N)
  exit()
max_count = 0
for i in range(0,len(a)-K+1):
  count = sum(a[i:i+K])
  if i==0:
    count+=sum(b[i:i+K])
  else:
    count+=sum(b[i-1:i+K])
  max_count = max(count, max_count)
print(max_count)

### FIXED CODE ###

N,K = map(int,input().split())
S = input()+"w"
A = []
if S[0]=="0":A.append(0)
a,b = 0,""
for s in S:
    if b!="" and b!=s:
        A.append(a)
        a=1
    else:a+=1
    b=s
if S[-2]=="0":A.append(0)
B = [0]
for i in range(len(A)):
    B.append(B[i]+A[i])
ans = 0
N = len(B)
for i in range(2*K+1,N):
    if i%2==0:continue
    ans = max(ans,B[i]-B[i-2*K-1])
print(ans if ans else B[N-1])
### BUGGY CODE ###

h, w = map(int, input().split())

grid = []
for _ in range(h):
    grid.append([x == '#' for x in input()])

maxd = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] is False:
            mind = 10000000
            for ii in range(h):
                for jj in range(w):
                    if grid[ii][jj] is True:
                        d = abs(i - ii) + abs(j - jj)
                        if d < mind:
                            mind = d
            if mind > maxd:
                maxd = mind

print(maxd)


### FIXED CODE ###

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

print(cnt - 1)
### BUGGY CODE ###

k,s=map(int,input().split())
x=0
b=0
for x in range(k+1):
  y=0
  while x+y<=s and y<=k:
    z=s-x-y
    if z>=0 and z<=k:
      b=b+1
    y=y+1
print(b)
      

### FIXED CODE ###

k,s=map(int,input().split())
x=0
b=0
while x<=k and x<=s//3:
  y=x
  while x+y<=s and y<=k and y<=(s-x)//2:
    z=s-x-y
    if z>=0 and z<=k:
      if x==y and y==z:
        b=b+1
      elif x==y:
        b=b+3
      elif y==z:
        b=b+3
      else:
        b=b+6
    y=y+1
  x=x+1
print(b)
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
countdic = Counter(A)
nCrdic = {}

for key,value in countdic.items():
    nCrdic[key] = (value*(value-1))//2 if value > 1 else 0
for i in A:
    if countdic[i] > 2:
        ans = sum(nCrdic.values()) - nCrdic[i] + ((countdic[i]-1)*(countdic[i]-2))//2
    else: ans = sum(nCrdic.values()) - nCrdic[i]
    print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
countdic = Counter(A)
goukei = 0
ans = ''
for key,value in countdic.items():
    goukei += (value*(value-1))//2
for i in A:
    ans = goukei -(countdic[i]*(countdic[i]-1))//2 + ((countdic[i]-1)*(countdic[i]-2))//2
    print(ans)
### BUGGY CODE ###

s=input();n=len(s);t=1;p=0;c=[0]*2019;r=0
for i in range(n+1):p=((ord(s[n-i])-ord("0")if i>0 else 0)*t+p)%2019;r+=c[p];c[p]+=1;t*=10
print(r)

### FIXED CODE ###

import sys

M = 2019
S = sys.stdin.readline().rstrip()
N = len(S)

dmod = [0] * (N + 1)
amod = [0] * (N + 1)
tenmod = 1
prev_amod = 0
mcnt = [0] * 2019
ans = 0
for i in range(N, -1, -1):
    d = ord(S[i]) - ord("0") if i < N else 0
    dmod[i] = d * tenmod % M
    amod[i] = (dmod[i] + prev_amod) % M
    ans += mcnt[amod[i]]
    mcnt[amod[i]] += 1
    tenmod = tenmod * 10 % M
    prev_amod = amod[i]
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
res = list(map(int,input().split()))
a = Counter(res)
for i in range(len(res)):
    a[res[i]] -= 1
    sums = 0
    for j in a.values():
        sums += j * (j - 1) // 2
    a[res[i]] += 1
    res[i] = sums
for k in res:
    print(k)

### FIXED CODE ###

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

sums = 0

for i in a.values():
    sums +=  i * (i - 1) // 2

for j in res:
    print(sums - a[j] * (a[j] -1) //2 + (a[j]-1) * (a[j] -2 ) // 2)
### BUGGY CODE ###

import math
n,k = map(int,input().split())
a = list(map(int,input().split()))

if k == 0:
	print(max(a))
	exit()

suki = 1000000000
kirai = 0
while int(suki) != int(kirai):
	targ = (suki+kirai)/2
	cnt = 0
	mode = 1
	for i in range(n):
		cnt += math.ceil(a[i] / targ)-1
		if cnt > k:
			mode = 0
			break
	if mode:
		suki = targ
	else:
		kirai = targ

print(math.ceil(suki))

### FIXED CODE ###

import math
n,k = map(int,input().split())
a = list(map(int,input().split()))

if k == 0:
	print(max(a))
	exit()

suki = 1000000000
kirai = 0
while int(suki) != int(kirai):
	targ = (suki+kirai)/2
	cnt = 0
	mode = 1
	for i in range(n):
		cnt += (a[i]-1)//targ
		if cnt > k:
			mode = 0
			break
	if mode:
		suki = targ
	else:
		kirai = targ

print(math.ceil(suki))
### BUGGY CODE ###

from collections import Counter
import sys
s = input()
N = len(s)
sc = Counter(s)
odds = sum([1 for x in sc if sc[x] % 2 == 1])
if odds > 1:
    print(-1)
    sys.exit(0)

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size+1)
    def add(self, index, elem):
        index += 1
        while index < len(self.bit):
            self.bit[index] += elem
            index += index & -index
    def get(self, index):
        index += 1
        ret = 0
        while 0 < index:
            ret += self.bit[index]
            index -= index & -index
        return ret



indices = [-1] * N
tb = {}
p = 0
for i in range(N):
    c = s[i]
    if c not in tb:
        indices[p] = i
        tb[c] = [p]
        p += 1
        continue
    l = len(tb[c])
    if 2 * l < sc[c]:
        indices[p] = i
        tb[c].append(p)
        p += 1
    elif 2 * l == sc[c] + 1:
        indices[N//2] = i
    else:
        indices[N-1-tb[c][sc[c]-l-1]] = i
        tb[c].append(p)

ans = 0
bit = BIT(N)
for i in indices:
    bit.add(i, 1)
    ans += bit.get(N-1) - bit.get(i)
print(ans)


### FIXED CODE ###

from collections import Counter
import sys
s = input()
N = len(s)
sc = Counter(s)
odds = [1 for x in sc if sc[x] % 2 == 1]
if len(odds) > 1:
    print(-1)
    sys.exit(0)

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size+1)
    def add(self, index, elem):
        index += 1
        while index < len(self.bit):
            self.bit[index] += elem
            index += index & -index
    def get(self, index):
        index += 1
        ret = 0
        while 0 < index:
            ret += self.bit[index]
            index -= index & -index
        return ret

indices = [-1] * N
tb = {c: [None] * (sc[c]//2) for c in sc}
lens = {c: 0 for c in sc}
p = 0
for i in range(N):
    c = s[i]
    l = lens[c]
    if 2 * (l+1) <= sc[c]:
        indices[p] = i
        tb[c][l] = p
        lens[c] += 1
        p += 1
    elif 2 * (l+1) == sc[c] + 1:
        indices[N//2] = i
        lens[c] += 1
    else:
        indices[N-1-tb[c][sc[c]-l-1]] = i
        lens[c] += 1

ans = 0
bit = BIT(N)
for i in indices:
    bit.add(i, 1)
    ans += bit.get(N-1) - bit.get(i)
print(ans)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr_lists = []
for i in range(Q):
    lr = list(map(int,input().split()))
    lr_lists.append(lr)

for i in range(Q):
    start = lr_lists[i][0] -1
    end = lr_lists[i][1] 
    str = S[start:end]
    

    count = 0
    """
    for j in range(0,len(str)-1):
        if str[j] == "A" and str[j+1] == "C":
            count += 1
    """
    count = str.count("AC")

    print(count)

### FIXED CODE ###

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

count_list = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == 'AC':
        count_list[i+1] = count_list[i] + 1
    else:
        count_list[i+1] = count_list[i]

for i in range(Q):
    l, r = map(int,input().split())
    print(count_list[r-1] - count_list[l-1])
### BUGGY CODE ###

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

cnt = 0
for x in range(K + 1):
    if x > S:
        break
    for y in range(K + 1):
        if x + y > S:
            break
        for z in range(K + 1):
            if x + y + z == S:
                cnt += 1
            elif x + y + z > S:
                break

print(cnt)

### FIXED CODE ###

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

cnt = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
s = list(map(int, input()))

a = [[set() for j in range(10)] for i in range(10)]
l = set()
for i in range(1, len(s) - 1):
    t = s[i]
    l.add(s[i-1])
    r = set(s[i+1:])
    for j in l:
        a[t][j] |= r

ans = 0
for b in a:
    for c in b:
        ans += len(c)
print(ans)

### FIXED CODE ###

n = int(input())
s = list(map(int, input()))

rr = {}
r = set()
for i in range(len(s) - 1, 0, -1):
    t = s[i]
    r.add(t)
    rr[i] = r.copy()

a = [[set() for j in range(10)] for i in range(10)]
l = set()
for i in range(1, len(s) - 1):
    t = s[i]
    l.add(s[i-1])
    r = rr[i+1]
    for j in l:
        a[t][j] |= r

ans = 0
for b in a:
    for c in b:
        ans += len(c)
print(ans)
### BUGGY CODE ###

while True:
	n = int(raw_input())
	if n == 0: break
	field = [raw_input() for i in range(n)]
	flag = 0
	for len in range(n,-1,-1):
		for row in range(n-len+1):
			for sp in range(n-len+1):
				if field[row][sp:sp+len] == "."*len:
					for i in range(1,len):
						if field[row+i][sp:sp+len] != "."*len:
							if len == 1:
								print 0
							break
					else:
						print len
						flag = 1
				if flag: break
			if flag: break
		if flag: break

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    field = [raw_input() for i in range(n)]
    large = [[0]*(n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if field[i][j] == '.':
                large[i][j] = min(large[i][j - 1], large[i - 1][j], large[i - 1][j - 1]) + 1
    print max(map(max, large))