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

import sys

S = input()
Q = int(input())
Flag = True
 
for i in range(Q):
    Query = input()
    if Query[0] == "1":
        Flag = not Flag
    else:
        QueryList = Query.split()
        if Flag:
            if QueryList[1] =="1":
                S = QueryList[2]+S
            else:
                S = S+QueryList[2]
        else:
            if QueryList[1] =="2":
                S = QueryList[2]+S
            else:
                S = S+QueryList[2]

if not Flag:
    S = S[::-1]    
print(S)
    

### FIXED CODE ###

from collections import deque

d = deque()
S = input()
d.append(S)
Q = int(input())
Flag = True
 
for i in range(Q):
    Query = input()
    if Query[0] == "1":
        Flag = not Flag
    else:
        QueryList = Query.split()
        if Flag:
            if QueryList[1] =="1":
                d.appendleft(QueryList[2])
            else:
                d.append(QueryList[2])
        else:
            if QueryList[1] =="2":
                d.appendleft(QueryList[2])
            else:
                d.append(QueryList[2])

d_string = "".join(list(d))

if not Flag:
    d_string = d_string[::-1]    
print(d_string)
### BUGGY CODE ###

import sys
import math
import numpy as np
pos=input()
pos=pos.split()
N=int(pos[0])
M=int(pos[1])

item=input()
item=item.split()
item=[float(d) for d in item]
npitem=np.array(item)
for i in np.arange(1,M+1):
  npitem[np.argmax(npitem)]=np.floor(np.max(npitem)/2.0)
    
print(int(np.sum(npitem)))








### FIXED CODE ###

import sys
import math
import numpy as np
from heapq import heappush, heappop
pos=input()
pos=pos.split()
N=int(pos[0])
M=int(pos[1])
sum=0

item=input()
item=item.split()
item=list(map(float,item))

hq=[]
for i in item:
  heappush(hq,-i)
  
for j in range(1,M+1):
  temp=heappop(hq)
  heappush(hq,math.ceil(temp/2.0))
  
for k in range(0,N):
  sum-=heappop(hq)
print(int(sum))
### BUGGY CODE ###

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

def Maze_Master(y, x, c):
    if y < 0 or y > h-1 or x < 0 or x > w-1 or m[y][x] != 0 and m[y][x] < c or s[y][x] == "#":
        pass
    else:
        m[y][x] = c
        c += 1
        Maze_Master(y+1, x, c)
        Maze_Master(y-1, x, c)
        Maze_Master(y, x+1, c)
        Maze_Master(y, x-1, c)
    return m
    
a = 0
for y in range(h):
    for x in range(w):
        m = [[0]*w for _ in range(h)]
        ans = Maze_Master(x, y, 1)
        l = []
        for i in ans:
            l.append(max(i))
        b = max(l)
        a = max(a, b)

print(a-1)

### FIXED CODE ###

import queue

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

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            t = [["."]*w for _ in range(h)]
            t[i][j] = 0
            q = queue.Queue()
            q.put((j, i))
            while True:
                x, y = q.get()
                for k, l in (1, 0), (-1, 0), (0, 1), (0, -1):
                    if (0 <= x+k and x+k < w and
                        0 <= y+l and y+l < h and
                        s[y+l][x+k] == "." and t[y+l][x+k] == "."):
                            t[y+l][x+k] = t[y][x] + 1
                            q.put((x+k, y+l))
                            
                if q.empty():
                    ans = max(ans, t[y][x])
                    break
print(ans)
### BUGGY CODE ###

s=input()
t=input()



#print(index)
condition=0
t2=list(set(t))
#print(t2)

for i in range(len(t2)):
 if s.count(t2[i])==0:
   condition=1
   break

if condition==1:
  print(-1)
else:
  index=list()
  for a in range(len(t)):
   index.append([i for i, x in enumerate(s) if x == t[a]])
  
  #print(index)
  b=index[0][0]
  j=1
  loop=0
  count=0
  if len(t)==1:
    print(b+1)
  else:
   while j <= len(t)-1:
     cond=0
     for k in range(len(index[j])):
       if index[j][k]+loop >b:
         b=index[j][k]+loop
         #print(b)
         j=j+1
         cond=1
         if j==len(t):
           print(b+1)
         break
       if cond==0:   
         loop=loop+len(s)
         if loop == len(s)*(10**100):
            print(-1)
            break
        



### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)
### BUGGY CODE ###

from __future__ import (absolute_import, division, print_function,
                        unicode_literals)
from sys import stdin

while True:
    n = int(stdin.readline())
    if not n:
        break

    tup = tuple(int(stdin.readline()) for _ in xrange(n))
    L = [tup[0]]
    for i in tup[1:]:
        if 0 > i and 0 > L[-1]:
            L[-1] += i
        elif 0 <= i and 0 <= L[-1]:
            L[-1] += i
        else:
            L.append(i)

    while True:
        length = len(L)
        if length > 1 and L[0] <= 0:
            L.pop(0)
            continue
        if length > 1 and L[-1] <= 0:
            L.pop()
            continue
        if length > 1 and L[0] + L[1] <= 0:
            L.pop(0)
            L.pop(0)
            continue
        if length > 1 and L[-1] + L[-2] <= 0:
            L.pop()
            L.pop()
            continue
        break
    print(L)

    m = 0
    for i in xrange(len(L)):
        for j in xrange(1 + i, len(L) + 1):
            t = sum(L[i:j])
            if t > m:
                m = t
    print(m)

### FIXED CODE ###

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from array import array

def grouping(nums):
    sign = None
    L = array(b'i')
    for s, n in ((i < 0, i) for i in nums):
        if sign is s:
            L[-1] += n
        else:
            sign = s
            L.append(n)

    if len(L) and L[-1] <= 0:
        del L[-1]
    if len(L) and L[0] <= 0:
        del L[0]
    return L

while True:
    n = int(stdin.readline())
    if not n:
        break

    L = array(b'i', (int(stdin.readline()) for _ in xrange(n)))
    val = max(L)
    if val <= 0:
        print(val)
        continue

    ans, temp = 0, 0
    for i in grouping(L):
        temp = max(0, temp+i)
        ans = max(ans, temp)
    print(ans)
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    t = set()
    no_dup = list(set([x for x in A if x in t or t.add(x)]))
    square_list = []
    for i in no_dup:
        if 4 <= A.count(i):
            square_list.append(i)

    no_dup.sort(reverse=True)
    if len(no_dup) == 0:
        print(0)
    else:
        if len(square_list) == 0:
            square_area = 0
        else:
            square_max = max(square_list)
            square_area = square_max * square_max
            
        if len(no_dup) == 1:
            rectan_area = 0
        else:
            rectan_area = no_dup[0] * no_dup[1]
            
        if square_area < rectan_area:
            print(rectan_area)
        else:
            print(square_area)


### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    A.sort(reverse=True)

    v = []
    while len(A) > 1:
        if len(v) == 2:
            break

        if A[0] == A[1]:
            v.append(A[0])
            A.pop(0)
            A.pop(0)
        else:
            A.pop(0)

    if len(v) == 1 or len(v) == 0:
        print(0)
    else:
        print(v[0] * v[1])
### BUGGY CODE ###

N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
A.sort()
count = 0
for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(len(A)-count)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[-1]
count = 0
cnt_list = [1] * ((10 ** 6) + 1)
for i in range(len(A_list)-1):
    if cnt_list[A_list[i]] == 1:
        for j in range((A_max // A_list[i]) + 1):
            cnt_list[A_list[i] * j] = 0
        if A_list[i] != A_list[i+1]:
            count += 1
if cnt_list[A_list[-1]] == 1:
    count += 1
print(count)
### BUGGY CODE ###

import collections

def main(A):
    return collections.Counter(A)


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    # N = 7
    # A = list(map(int, "1 2 3 4 5 6".split()))
    [print(main(A)[i + 1]) for i in range(N)]


### FIXED CODE ###

import collections

def main(N, A):
    c = collections.Counter(A)
    [print(c[i+1]) for i in range(max(c.keys()))]
    [print(0) for i in range(max(c.keys()), N)]

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    # N = 7
    # A = list(map(int, "1 2 3 4 5 6".split()))
    main(N, A)
### BUGGY CODE ###

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

### FIXED CODE ###

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    
    if 0 in nums:
        print(0)
        return
    
    mul = 1
    for i in nums:
        mul *= i
        if mul > 1000000000000000000:
            print(-1)
            return
        
    print(mul)
    
main()
### BUGGY CODE ###

import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

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

#i+j>k and i+k>j and j+k>i

N_2 = int(N/2)+1

L.sort()

ans=0
for i in range(0, N-1):
	for j in range(1, N-1):
		for k in range(N-1, N_2-3, -1):
			#print(i,j,k,'=',L[i],L[j],L[k])
			if i>=j or j>=k or i>=k:
				#print('skip')
				continue
			elif L[i]+L[j]>L[k]:
				ans+=1
				#print('here')
print(ans)

### FIXED CODE ###

import sys
import bisect

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

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

ans=0
for i in range(0, N-1):
	for j in range(1, N-1):
		if i>=j:
			continue
		ans += bisect.bisect_left(L, L[i]+L[j], lo=j+1)-1-j
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n+1):
    print(a.count(i))

### FIXED CODE ###

from collections import Counter, deque
n = int(input())
a = deque(list(map(int, input().split())))
c = Counter(a)
for i in range(1, n+1):
    if i in c.keys():
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

import math
from functools import reduce
from collections import deque, Counter
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def prime_factorize(n):
    """
    素因数分解
    
    Sample:
        prime_factorize(36)
        => [2, 2, 3, 3]

        collections.Counter(prime_factorize(36))
        => {2:2, 3:2}
    """
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

    if len(arr) == 0:
        arr.append((n, 1))
    return arr

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()
C = dict(Counter(A))
# log(C)

ans = 0

for i,a in enumerate(A):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            if C[d] > 1:
                # log(C[d])
                ok = False
                break
        elif d in C:
            ok = False
            break
    if ok:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

print(ans)
### BUGGY CODE ###

import numpy as np

H, N = map(int, input().split())
#dp = [ float("inf") for _ in range(H+1)]
dp = np.array([float("inf")]*(H+1))
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

    
print(int(dp[H]))

### FIXED CODE ###

H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])
### BUGGY CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        if z[i]==0:
                            z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

def main():
    n,q = list(map(int,input().split(' ')))
    s = input()
    s_tr =[]
    q_list = []
    for i in range(n-1):
        if len(s_tr) !=i:
            continue
        if s[i] == 'A' and s[i+1] =='C':
            s_tr.append(1)
            s_tr.append(1)
        else:
            s_tr.append(0)
    if len(s_tr) < n:
        s_tr.append(0)

 

    for i in range(q):
        l,r = list(map(int,input().split(' ')))
        if l ==1 or r ==n:
            print(sum(s_tr[l-1:r])//2)
        else:
            if s_tr[l-2] ==0 or s_tr[r] ==0:
                print(sum(s_tr[l-1:r])//2)
            else:
                print(sum(s_tr[l-1:r])//2 -1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n,q = list(map(int,input().split(' ')))
    s = input()
    tmp = 0
    s_tr =[]
    q_list = []
    for i in range(n-1):
        if len(s_tr) !=i:
            continue
        if s[i] == 'A' and s[i+1] =='C':
            tmp += 1
            s_tr.append(tmp)
            s_tr.append(tmp)
        else:
            s_tr.append(tmp)
    if len(s_tr) != n:
        s_tr.append(tmp)
    for i in range(q):
        q_list.append(list(map(int,input().split(' '))))

    for l,r in q_list:
        if s_tr[r-1] ==s_tr[r-2]:
            if l ==1:
                print(s_tr[r-1])
            else:
                print(s_tr[r-1]-s_tr[l-2])
        else:
            if l ==1:
                print(s_tr[r-1] - 1)
            else:
                print(s_tr[r-1] - s_tr[l-2] -1 )

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

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    N = int(input())
    A = input_nums()
    C = collections.Counter(A)

    X = {}
    Y = {}

    for k, v in C.items():
        if v >= 2:
            X[k] = cmb(v, 2)
        else:
            X[k] = 0
        if v >= 3:
            Y[k] = cmb(v-1, 2)
        else:
            Y[k] = 0

    for i in range(N):
        val = 0
        for k in X.keys():
            if A[i] == k:
                val += Y[k]
            else:
                val += X[k]
        print(val)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    N = int(input())
    A = input_nums()
    C = collections.Counter(A)

    X = {}
    Y = {}
    maxv = 0
    for k, v in C.items():
        if v >= 2:
            X[k] = cmb(v, 2)
            maxv += X[k]
        else:
            X[k] = 0
        if v >= 3:
            Y[k] = cmb(v-1, 2)
        else:
            Y[k] = 0

    ANS = {}
    for k in Y.keys():
        ANS[k] = maxv - (X[k] - Y[k])

    for a in A:
        print(ANS[a])

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

def readln():
    return list(map(int, input().split()))


A, B = readln()

ans = []
for i in range(40):
    power = 1 << i  # i桁目について考える
    bit_count_of_1 = sum(1 for a in range(A, B + 1) if a & power != 0)
    if bit_count_of_1 % 2 == 1:
        ans.append(1)
    else:
        ans.append(0)

ans_print = 0
for i, a in enumerate(ans):
    ans_print += 2 ** i if a == 1 else 0

print(ans_print)


### FIXED CODE ###

def readln():
    return list(map(int, input().split()))


A, B = readln()


A_isodd = []  # 奇数の桁は1
B_isodd = []  # 奇数の桁は1
# 1の偶奇
tmp = (A) % 4
if (tmp == 2)or(tmp == 3):
    A_isodd.append(1)
else:
    A_isodd.append(0)
tmp = (B+1) % 4
if (tmp == 2)or(tmp == 3):
    B_isodd.append(1)
else:
    B_isodd.append(0)


for i in range(1, 40):  # 各桁につい
    tmp = (A) % 2 ** (i + 1)
    if (tmp > 2 ** (i)) and (tmp % 2 == 1):
        A_isodd.append(1)
    else:
        A_isodd.append(0)
    tmp = (B + 1) % 2 ** (i + 1)
    if (tmp > 2 ** (i)) and (tmp % 2 == 1):
        B_isodd.append(1)
    else:
        B_isodd.append(0)

# print(A_isodd)
# print(B_isodd)

ans = []
for a, b in zip(A_isodd, B_isodd):
    if a == b:
        ans.append(0)
    else:
        ans.append(1)

ans_print = 0
for i, a in enumerate(ans):
    ans_print += 2 ** i if a == 1 else 0

print(ans_print)
### BUGGY CODE ###


def main():
    N, M = map(int, input().split())
    lr = [list(map(int, list(input().split()))) for i in range(M)]
    # N, M = 4, 2
    # lr = [[1, 3], [2, 4]]

    count = 0

    for i in range(N):
        f = check(lr, i + 1)
        if f:
            count += 1
    print(count)


def check(lr: list, card: int):
    for line in lr:
        f = line[0] <= card <= line[1]
        if not f:
            return False
    return True


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    lr = [list(map(int, list(input().split()))) for i in range(M)]
    # N, M = 4, 2
    # lr = [[1, 1], [3, 4]]
    ll = []
    rl = []
    for line in lr:
        ll.append(line[0])
        rl.append(line[1])
    diff = min(rl) - max(ll)
    if diff < 0:
        print(0)
        return
    print(diff + 1)


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

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in range(n-solve):
                for x in range(n-solve):
                    if dp[y][x]==solve:
                        old=dp[y][x]
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        if old !=dp[y][x]:
                            flag=1
            if flag==0:
                break
            solve+=1
        print solve

### FIXED CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n+1)]for j in range(n+1)]
    for i in range(1,n+1):
        j=0
        line=" "+raw_input()
        for c in line:
            if c == ".":
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            j+=1
    allmax=0
    for i in range(n+1):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax