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

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

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
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)]

n = int(input())

keta = int(math.log10(n)) + 1

memo = [ [None] * 10 for _ in range(10)]

ans = 0
for a in range(1, n+1):
    x = int(str(a)[0])
    y = a % 10

    if x == 0 or y == 0:
        continue

    if memo[x][y] is not None:
        ans += memo[x][y]
        # print(a, ans)
        continue
    
    patterns = 0
    for b in range(1, n+1):
        x2 = int(str(b)[0])
        y2 = b % 10
        if x == y2 and y == x2:
            patterns += 1
    memo[x][y] = patterns
    ans += patterns
    # print(a, ans)

    # patterns = 0
    # # 1桁
    # if x == y and n <= x:
    #     patterns += 1
    
    # for k in range(keta-1):

print(ans)

### FIXED CODE ###

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

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
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)]

n = int(input())

keta = int(math.log10(n)) + 1

memo = [ [None] * 10 for _ in range(10)]

ans = 0
for a in range(1, n+1):
    x = int(str(a)[0])
    y = a % 10

    if x == 0 or y == 0:
        continue

    if memo[x][y] is not None:
        ans += memo[x][y]
        # print(a, ans)
        continue
    
    patterns = 0
    for b in range(x, n+1, 10):
        x2 = int(str(b)[0])
        y2 = b % 10
        if x == y2 and y == x2:
            patterns += 1
    memo[x][y] = patterns
    ans += patterns
    # print(a, ans)

    # patterns = 0
    # # 1桁
    # if x == y and n <= x:
    #     patterns += 1
    
    # for k in range(keta-1):

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

from collections import OrderedDict 
n=int(input())
d={}
for i in range(n):
    s=str(input())
    if(s not in d):
        d[s]=1
    else:
        d[s]=d[s]+1
d = OrderedDict(sorted(d.items()))
for j,k in d.items():
    if (k==max(d.values())):
        print(j)

### FIXED CODE ###

N = int(input())
dic = {}
for i in range(N):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
max_val = max(dic.values())
rst = [ key for key, val in dic.items() if val == max_val ]
[ print(i) for i in sorted(rst) ]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
T = [[] for i in range(N+1)]
V = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
def f(v,p):
    global T,V
    for c in T[v]:
        if c==p:continue
        V[c]+=V[v]
        f(c,v)
f(1,0)
print(*V[1:])

### FIXED CODE ###

N,Q = map(int,input().split())
T = [0]*(N+1)
V = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    T[b] = a
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
for i in range(1,N+1):
    V[i]+=V[T[i]]
print(*V[1:])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1

for i in range(n):
    ans*=a[i]
    

if ans<=10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=1

for i in range(n):
    ans*=a[i]
    if ans==0 or ans>10**18:
        break

    

if ans<=10**18:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
ss = []
cnt = 0

# for _ in range(n):
#     ss.append(input())

# for i, s1 in enumerate(ss[0:n-2+1]):
#     for s2 in ss[i + 1:n-1+1]:
#         # print(s1, s2)
#         if sorted(s1) == sorted(s2):
#             cnt += 1

for _ in range(n):
    ss.append(input())

map = {}
for s in ss:
    sorted_s = ''.join(sorted(s))
    if sorted_s in map.keys():
        map[sorted_s] += 1
    else:
        map[sorted_s] = 1


# map = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# map = {'a': 10 ** 5}  # maxテスト
# print(map)

# def factorial(n):
#     if n > 0:
#         return n * factorial(n-1)
#     else:
#         return 1


def factorial(x):
    ans = 1
    for i in range(2, x+1):
        ans *= i
    return ans

# あとはxC2の組み合わせの総数を求めれば良い


for n in map.values():
    if n > 1:
        cnt += factorial(n) // (2 * factorial(n-2))
    # print(n)
    # print(cnt)

print(cnt)

### FIXED CODE ###

n = int(input())
ss = []
cnt = 0

# for _ in range(n):
#     ss.append(input())

# for i, s1 in enumerate(ss[0:n-2+1]):
#     for s2 in ss[i + 1:n-1+1]:
#         # print(s1, s2)
#         if sorted(s1) == sorted(s2):
#             cnt += 1

for _ in range(n):
    ss.append(input())

map = {}
for s in ss:
    sorted_s = ''.join(sorted(s))
    if sorted_s in map.keys():
        map[sorted_s] += 1
    else:
        map[sorted_s] = 1


# map = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# map = {'a': 10 ** 5}  # maxテスト
# print(map)

# あとはxC2の組み合わせの総数を求めれば良い


for n in map.values():
    if n > 1:
        # cnt += factorial(n) // (2 * factorial(n-2))
        cnt += (n * (n - 1)) // 2
    # print(n)
    # print(cnt)

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

from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    if left % 2 == 0:
        left += 1
    print(len([n for n in range(left, right + 1, 2) if is_prime(n) and is_prime((n + 1) // 2)]))


### FIXED CODE ###

from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


size = 10 ** 5 + 1
memo = [0] * size
for n in range(3, size):
    memo[n] = memo[n - 1]
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        memo[n] += 1

Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    print(memo[right] - memo[left - 1])
### BUGGY CODE ###

#coding:utf-8
import math
import itertools
from functools import reduce

def gcd(num):
    return reduce(math.gcd, num)

def main():
    k = int(input())
    ans = 0

    num = [i for i in range(1,k+1)]
    comb = tuple(itertools.product(num, repeat=3))


    for i in comb:
        ans += gcd(i)

    print(ans)

if __name__ == "__main__":
    main()



### FIXED CODE ###

#coding:utf-8
from math import gcd

def main():
    k = int(input())
    ans = 0

    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1, k+1):
                ans += gcd(gcd(a, b), c)

    print(ans)

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

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

stack=[]

import copy

stack.append([0,[],-1])
Nhalf=None
while stack:
  node=stack.pop()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    route.append(v)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
    E[Nhalf].remove(NhalfNext)
    E[NhalfNext].remove(Nhalf)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    stack.append([child,newroute,v])
  del route

stack=[]
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
if count>N-count:
  print("Fennec")
else:
  print("Snuke")

### FIXED CODE ###

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

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

FenWin=0
SunWin=0
for i in range(N):
  if F[i]<=S[i]:
    FenWin+=1
  else:
    SunWin+=1
print(("Snuke","Fennec")[FenWin>SunWin])
### BUGGY CODE ###

from sys import stdin
from itertools import takewhile
        
N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().split()]
L.sort()

ans = 0
for a in range(len(L)-2):
    for b in range(a + 1, len(L)-1):
        ab = L[a] + L[b]
        c = list(takewhile(lambda x: x < ab, L[b+1:]))
        ans += len(c)

print(ans)

### FIXED CODE ###

from sys import stdin
import bisect
        
N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().split()]
L.sort()

ans = 0
for a in range(len(L)-2):
    for b in range(a + 1, len(L)-1):
        c = bisect.bisect_left(L, L[a] + L[b])
        if c > b:
            ans += c - 1 - b

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

# 1 <= N <= 10**5
# N <= M <= 10**9
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())

V = M // N

ans = 1
for i in range(1, V + 1):
    if M % i == 0:
        ans = i
print(ans)


### FIXED CODE ###

# 1 <= N <= 10**5
# N <= M <= 10**9
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())

V = M // N

ans = 1
for i in range(1, V + 1):
    if i * i > M:
        break
    if M % i == 0:
        j = M // i
        if j <= V:
            ans = max(ans, j)
        else:
            ans = max(ans, i)
print(ans)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
L = sorted(map(int, input().split()))

def binary_search(imin, imax, target):
    if imin > imax:
        return imin

    imid = (imin + imax) // 2
    if L[imid] == target:
        return imid
    elif L[imid] < target:
        return binary_search(imid+1, imax, target)
    else:
        return binary_search(imin, imid-1, target)

counter = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        # 許容されるcの値は
        # L[j] < c
        # c < L[i] + L[j]
        upper_bound = binary_search(j+1, N-1, L[i] + L[j])
        counter += upper_bound - (j+1)
print(counter)

### FIXED CODE ###

from itertools import combinations
from bisect import bisect_left

N = int(input())
L = sorted(map(int, input().split()))

counter = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        upper_bound = bisect_left(L, L[i] + L[j], j+1, N)
        counter += upper_bound - (j+1)
print(counter)
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(200000)
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
inf=float("inf")
Par=[inf]*n
Par[0]=-1
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Chk.append(next)

C=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==Par[x]:
        continue
      else:
        ret+=ch(e)+1
    C[x]=ret
    return C[x]
ch(0)

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur=(cur-H[n-1-a])%mod
    ans=(ans+cur)%mod
print((ans*H[1])%mod)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(200000)
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
inf=10**6
Par=[inf]*n
Par[0]=-1
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Chk.append(next)

C=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==Par[x]:
        continue
      else:
        ret+=ch(e)+1
    C[x]=ret
    return C[x]
ch(0)

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)
### BUGGY CODE ###

def main():
    N,M=map(int, input().split())
    l =[set() for _ in range(N)]
    for _ in range(M):
        a,b=map(int, input().split())
        for s in l:
            if s:
                if a in s or b in s:
                    s.add(a)
                    s.add(b)
                    break
            else:
                s.add(a)
                s.add(b)
                break
    ans=-1
    for s in l:
        if not(s):
            break
        ans=max(ans,len(s))
    if ans==-1:
        print(1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents=[-1 for _ in range(n)]
    
    def find(self,n):
        x=self.parents[n]
        if x<0:
            return n
        else:
            self.parents[n]=self.find(self.parents[n])
            return self.parents[n]
    
    def union(self,n,m):
        x=self.find(n)
        y=self.find(m)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x

sys.setrecursionlimit(10**9)    
n,m=map(int,input().split())
uf=UnionFind(n)

for _ in range(m):
    a,b=map(lambda x: int(x)-1, input().split())
    uf.union(a,b) 

ans=0

for p in uf.parents:
    ans=min(ans,p)

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

N = int(input())
min = N - 1
for i in range(1, N // 2):
    if N % i == 0:
        j = N // i
        if (i -1) + (j - 1) < min:
            min = (i - 1) + (j - 1)

print(min)




### FIXED CODE ###

import math

N = int(input())
for i in range(1, int(math.sqrt(N) + 1))[::-1]:
    if N % i == 0:
        print(N // i + i - 2)
        break
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    for _ in range(k):
        imos = [0]*(n+1)
        finish = True
        for i, brightness in enumerate(a):
            if finish and brightness != n:
                finish = False
            begin = max(i - brightness, 0)
            end = i + brightness
            imos[begin] += 1
            if end < n:
                imos[end + 1] -= 1
        if finish:
            break
        for i in range(n-1):
            imos[i+1] += imos[i]
        a = imos[:-1]
    print(*a, sep=" ")


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    for _ in range(k):
        imos = [0]*(n+1)
        finish = True
        for i, brightness in enumerate(a):
            if finish and brightness != n:
                finish = False
            begin = max(i - brightness, 0)
            end = i + brightness
            imos[begin] += 1
            if end < n:
                imos[end + 1] -= 1
        if finish:
            break
        for i in range(n-1):
            imos[i+1] += imos[i]
        a = imos[:-1]
    print(*a, sep=" ")


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

import math

n,p=map(int,input().split())

def C(N,P):
    if N == 1: return P
    b=int(math.log2(N))
    a=P**(1/b)

    res=1
    for i in range(2,int(a)+2):
        if i**N > P : break
        if P % i**N == 0 : res = i

    return res

print(C(n,p))

### FIXED CODE ###

n,p = list(map(int,input().split())) 
i = a = o = 1
m = round(p**(1/n))
for i in range(m,0,-1):
    a = i**n
    if p%a==0:
        print(i)
        exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
read = sys.stdin.read

def main():
  n, q = map(int, input().split())
  event = []
  stop = set()
  for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))
  event.sort()
  event.append((float("inf"), 0, 0))
  D = list(map(int, read().split()))
  now = 0
  for t, b, x in event:
    while t > D[now]:
      if stop:
        print(min(stop))
      else:
        print(-1)
      now += 1
      if now == q:
        exit()
    if b == 1:
      stop.add(x)
    else:
      stop.remove(x)
      
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
read = sys.stdin.read

import heapq

def main():
  n, q = map(int, input().split())
  event = []
  stop = set()
  minque = []
  for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))
  event.sort()
  event.append((float("inf"), 0, 0))
  D = list(map(int, read().split()))
  now = 0
  for t, b, x in event:
    while minque and minque[0] not in stop:
      heapq.heappop(minque)
    m = minque[0] if minque else -1
    while t > D[now]:
      print(m)
      now += 1
      if now == q:
        exit()
    if b == 1:
      stop.add(x)
      heapq.heappush(minque, x)
    else:
      stop.remove(x)
      
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N, K, Q = map(int, input().strip().split())
# A=[0]*Q
score=[K]*N
for i in range(Q):
    A=int(input().strip())
    score[A-1]+=1
    score=list(map(lambda x: x-1,score))

for i in range(N):
    if score[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().strip().split())
# A=[0]*Q
score=[K]*N
for i in range(Q):
    A=int(input().strip())
    score[A-1]+=1
score=list(map(lambda x: x-Q,score))

for i in range(N):
    if score[i]>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N,point,answer=list(map(int,input().split()))
W=[point]*N
for i in range(answer):
  U=int(input())
  W=[n-1 for n in W]
  W[U-1]+=1
for k in range(N):
  if W[k]<=0:
    print("No")
  else:
    print("Yes")
  
  
  
  

### FIXED CODE ###

N,point,answer=list(map(int,input().split()))
W=[point]*N
for i in range(answer):
  U=int(input())
  W[U-1]+=1
W=[n-answer for n in W]
for k in range(N):
  if W[k]<=0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

import bisect
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        t = bisect.bisect_left(l[j+1:], l[i] + l[j])
        k = bisect.bisect_left(l[j+1:], abs(l[i] - l[j]))
        ans += t - k
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        t = bisect.bisect_left(l, l[i] + l[j])
        if (t > j):
            ans += t - j - 1
print(ans)
### BUGGY CODE ###

Sstr = input()
stop=len(Sstr)
count=0
for i in range(stop-3):
    for j in range(i+3,stop):
        if(int(Sstr[i:j+1])%2019==0):
            count=count+1
print(count)

### FIXED CODE ###

p = 2019 
D = input()
n=(len(D))
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
Q = deque()
dist = [[99999]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if C[i][j] == "#":
      dist[i][j] = 0
      Q.append((i,j))
      while Q:
        y,x = Q.popleft()
        for k in range(4):
          ny = y + Y[k]
          nx = x + X[k]
          if not (0 <= nx < W):
            continue
          if not (0 <= ny < H):
            continue
          if not (C[ny][nx] == "."):
            continue
          if not (dist[ny][nx] > dist[y][x]+1):
            continue
          Q.append((ny,nx))
          dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "#":
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))
print(max(max(row) for row in dp))
### BUGGY CODE ###

def main():
    from fractions import gcd
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    # n,*a=map(int,open(0).read().split())
    mod=10**9+7
    b=max(a)
    for i in a:
        if b%i!=0:
            b=b*i//gcd(b,i)
    ans=0
    for i in a:
        ans+=b//i
        ans%=mod
    print(ans)    
    # print(sum(b//i%mod for i in a)%mod)    
if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

import sys

test = False
N = 100

def check(n):
    if test:
        if n<=N and str(n)<=str(N) or n>N and str(n)>str(N):
            return "Y"
        else:
            return "N"
    else:
        print "?", n
        return raw_input()

for d in range(11):
    if check(10**d)=="N":
        d -= 1
        break
if d==10:
    for i in range(1,11):
        if check(10**i-1)=="Y":
            print "!", 10**(i-1)
            break
else:
    l = 10**d
    r = 10**(d+1)
    while r-l>1:
        m = (l+r)/2
        if check(m*10)=="Y":
            r = m
        else:
            l = m
    print "!", r
sys.stdout.flush()


### FIXED CODE ###

import sys

test = False
N = 100

def check(n):
    if test:
        if n<=N and str(n)<=str(N) or n>N and str(n)>str(N):
            return "Y"
        else:
            return "N"
    else:
        print "?", n
        sys.stdout.flush()
        return raw_input()

for d in range(11):
    if check(10**d)=="N":
        d -= 1
        break
if d==10:
    for i in range(1,11):
        if check(10**i-1)=="Y":
            print "!", 10**(i-1)
            break
else:
    l = 10**d
    r = 10**(d+1)
    while r-l>1:
        m = (l+r)/2
        if check(m*10)=="Y":
            r = m
        else:
            l = m
    print "!", r
sys.stdout.flush()
### BUGGY CODE ###

while True:
    n = input()
    if n == 0:
        break
    A = [0]*7
    for _ in xrange(n):
        A[min(input()/10,6)] += 1
    print "\n".join(map(str,A))

### FIXED CODE ###

while True:
    n = input()
    if n == 0:
        break
    A = [0]*7
    for _ in xrange(n):
        A[min(int(raw_input())/10,6)] += 1
    print "\n".join(map(str,A))