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

import sys
sys.setrecursionlimit(int(1e7))
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

d=A+B+C
memo=[[[-1]*(d+1) for _ in range(d+1)] for _ in range(d+1)]
memo[0][0][0]=0
def c(i,j,k):
        if memo[i][j][k]!=-1:
            return memo[i][j][k]
        else:
            memo[i][j][k]=n/(i+j+k)
            if 1<=i<=d:
                memo[i][j][k]+=c(i-1,j,k)*i/(i+j+k)
            if 0<=i<=d-1 and 1<=j<=d:
                memo[i][j][k]+=c(i+1,j-1,k)*j/(i+j+k)
            if 0<=j<=d-1 and 1<=k<=d:
                memo[i][j][k]+=c(i,j+1,k-1)*k/(i+j+k)
            return memo[i][j][k]

print(c(A,B,C))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

dp=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
def c():
    for k in range(C+1):
        for j in range(B+C+1-k):
            for i in range(n+1-k-j):
                if i==0 and j==0 and k==0:
                    continue
                res=1.0*n
                if i>0:
                    res+=i*dp[i-1][j][k]
                if j>0:
                    res+=j*dp[i+1][j-1][k]
                if k>0:
                    res+=k*dp[i][j+1][k-1]
                dp[i][j][k]=res/(i+j+k)
    print(dp[A][B][C])
c()
### BUGGY CODE ###

from itertools import groupby
def main():
    n=int(input())
    aa=sorted(map(int,input().split()))
    d={}
    for k,g in groupby(aa):
        d[k] = len(list(g))
    q=int(input())
    bc=[]
    for _ in range(q):
        b,c=map(int,input().split())
        bc.append((b,c))
    for b,c in bc:
        if b in d:
            d[c] = d.setdefault(c, 0) + d[b]
            del d[b]
        print(sum(k*v for k,v in d.items()))
main()

### FIXED CODE ###

from itertools import groupby
def main():
    n=int(input())
    aa=sorted(map(int,input().split()))
    d={}
    for k,g in groupby(aa):
        d[k] = len(list(g))
    q=int(input())
    bc=[]
    for _ in range(q):
        b,c=map(int,input().split())
        bc.append((b,c))
    s = sum(k*v for k,v in d.items())
    for b,c in bc:
        if b in d:
            s += (c-b)*d[b]
            d[c] = d.setdefault(c, 0) + d[b]
            del d[b]
        print(s)
main()
### BUGGY CODE ###

if __name__ == "__main__":
    N=int(input())
    lis=list(map(int,input().split()))
    lis.sort()
    sum=0
    while(len(lis)>1):
        v=lis.pop()
        k=1
        while k<=v:
            k*=2
        m=k-v
        if m in lis:
            sum+=1
            lis.remove(m)

    print(sum)

### FIXED CODE ###

from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>0):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if x==y:
                ans+=mii[x]//2
            elif y<x and y in si:
                m=min(mii[x],mii[y])
                ans+=m
                mii[y]-=m
            mii[x]=0
    print(ans)
### BUGGY CODE ###

N,K =map(int,input().split())
result = []
for i in range(N):
  a,b = map(int,input().split())
  result +=[a]*b
result.sort()
print(result[K-1])

### FIXED CODE ###

N,K =map(int,input().split())
result = [0]*(10**5+1)
for i in range(N):
  a,b = map(int,input().split())
  result[a] += b
count = 0
for j in range(len(result)):
  count += result[j]
  if count >= K:
    print(j)
    break
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    x = a.index(max(a))
    a[x] //= 2
print(sum(a))

### FIXED CODE ###

import heapq as hq
n, m = map(int, input().split())
a = [-int(i) for i in input().split()]
hq.heapify(a)
for i in range(m):
    minprice = hq.heappop(a)
    hq.heappush(a, (-minprice // 2) * -1)
print(-sum(a))
### BUGGY CODE ###

import math
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
maxcomb=0
ans=[0,0]

def combination(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

for i in range(1):
    for j in range(i+1,n):
        comb=combination(a[i], a[j])
        if(maxcomb < comb):
            maxcomb = comb
            ans=[a[i],a[j]]
print(str(ans[0])+" "+str(ans[1]))

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2

ai=a[0]
temp=list(map(lambda x:abs(x-mid(ai)),a[1:]))
bi=a[temp.index(min(temp))+1]
print(str(ai)+" "+str(bi))
### BUGGY CODE ###

n = int(input())
S = input()
PIN = set()
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            PIN.add(S[i] + S[j] + S[k])
print(len(PIN))

### FIXED CODE ###

N=int(input())
s=input()
PIN=[]
firs=[]
sec=[]
thir=[]
for i in range(N-2):
    if s[i] not in firs:
        firs.append(s[i])
        for j in range(i+1,N-1):
            if s[j] not in sec:
                sec.append(s[j])
                for k in range(j+1,N):
                    if s[k] not in thir:
                        thir.append(s[k])
                        PIN.append(s[i]+s[j]+s[k])
                thir=[]
        sec=[]       
print(len(PIN))
### BUGGY CODE ###

import fractions
from functools import reduce

n = int(input())
a = [int(i) for i in input().split()]

def gcd(nums):
    return reduce(fractions.gcd, nums)

ans_l = []
for i in range(len(a)):
    aa = a[:i] + a[(i+1):]
    ans_l.append(gcd(aa))
ans = max(ans_l)
print(ans)

### FIXED CODE ###

import sys
from functools import reduce

input = sys.stdin.readline

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

n = int(input())
a = [int(i) for i in input().split()]


ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i], a[i])
    r[n-i-1] = gcd(r[n-i], a[n-i-1])
for i in range(n):
    ans = max(ans, gcd(l[i], r[i+1]))
print(ans)
### BUGGY CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

subtree_size = []
def dfs(node, parent):
    cnt = 1
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    if cnt != N:
        subtree_size.append(cnt)
    return cnt

dfs(0, None)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

ans = 0
for s in subtree_size:
    ans += (pow2[s] - 1) * (pow2[N-s] - 1)

ans = ans - N * pow2[N-1] + pow2[N] - 1
ans = ans * pow(pow2[N], mod - 2, mod) % mod

print(ans)

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

s = input()
dp = [0 for i in range(13)]
m = 1
dp[0] = 1
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for i in range(13)]
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                ndp[(j * m + k) % 13] += dp[k]
    else:
        j = int(s[i])
        for k in range(13):
            ndp[(j * m + k) % 13] += dp[k]
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5] % 1000000007)

### FIXED CODE ###

s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for _ in r13]
    if s[i] == "?":
        for j in r10:
            jm = j * m
            for k in r13:
                index = (jm + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        jm = int(s[i]) * m
        for k in r13:
            index = (jm + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

# スタック最大数をセット
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
a = [[j == '#' for j in input()] for _ in range(h)]

queue = deque([(i, j, 0) for i in range(h)
               for j in range(w) if a[i][j]])

ans = 0

dx = (1, 0, 0, -1)
dy = (0, 1, -1, 0)


def bfs(y, x, cnt):

    if (y < 0 or h <= y or x < 0 or w <= x or not a[y][x]):
        return
    #print(y, x, cnt)
    for ddx, ddy in zip(dx, dy):
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and not a[y+ddy][x+ddx]):
            a[y+ddy][x+ddx] = True
            queue.append((y + ddy, x+ddx, cnt+1))


while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])
    # print(queue)
print(ans)

### FIXED CODE ###

from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,M = map(int,input().split())
gcd = M // N
gcd_tmp = 0
for gcd in range(gcd,0,-1):
 if M % gcd == 0:
  break
print(gcd)

### FIXED CODE ###

def calc():
 N,M = map(int,input().split())
 for gcd in range(M // N,0,-1):
  if M % gcd == 0:
   break
 return(gcd)
print(calc())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod=10**9+7
n,m=map(int,input().split())
A=[]
for i in range(m):
  a=int(input())
  A.append(a)
S=[0]*(n+1)
S[0]=1
if 1 not in A:
  S[1]=1
for i in range(2,n+1):
  if i in A:
    S[i]=0
  else:
    S[i]=S[i-1]+S[i-2]
print(S[n]%mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline
mod=10**9+7
n,m=map(int,input().split())
A=set()
for i in range(m):
  A.add(int(input()))
S=[0]*(n+1)
S[0]=1
if 1 not in A:
  S[1]=1
for i in range(2,n+1):
  if i in A:
    S[i]=0
  else:
    S[i]=(S[i-1]+S[i-2])%mod
print(S[n]%mod)
### BUGGY CODE ###

import queue
H, W = map(int, input().split())
S = [list(input()) for h in range(H)]

Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            Visited = [[False for w in range(W)] for h in range(H)]
            Visited[h][w] = True
            Q = queue.Queue()
            Q.put((h,w))
            Count = 0
            while not Q.empty():
                now = Q.get()
                color = S[now[0]][now[1]]
                for s in Search:
                    if 0 <= now[0] + s[0] < H and 0 <= now[1]+s[1] < W:
                        if color == "#":
                            if S[now[0]+s[0]][now[1]+s[1]] == "." and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                Count += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
                        else:
                            if S[now[0]+s[0]][now[1]+s[1]] == "#" and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                Q.put((now[0]+s[0], now[1]+s[1]))
            Total += Count
print(Total)

### FIXED CODE ###

import queue
H, W = map(int, input().split())
S = [list(map(int, input().replace(".", "0").replace("#","1"))) for h in range(H)]

Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if not Visited[h][w]:
            Visited[h][w] = True
            Color = ([1, 0] if S[h][w] == 0 else [0, 1])
            Q = queue.Queue()
            Q.put((h, w, S[h][w]))
            while not Q.empty():
                nh, nw, nc = Q.get()
                for s in Search:
                    nexth, nextw = nh + s[0], nw + s[1]
                    if 0 <= nexth < H and 0 <= nextw < W:
                        if not Visited[nexth][nextw] and S[nexth][nextw] != nc:
                            nextc = S[nexth][nextw]
                            Visited[nexth][nextw] = True
                            Q.put((nexth, nextw, nextc))
                            Color[nextc] += 1
            Total += Color[0] * Color[1]

print(Total)
### BUGGY CODE ###

N=int(input())
s=sorted([sorted(list(input())) for i in range(N)])
count=0
l=[]
for i in range(N-1):
    if not s[i] in s[i+1:][0]:
        l.append(i)
l.append(N-1)
s=[ s[i] for i in range(N) if i in l  ]
s_l=len(s)

for i in range(s_l-1):
    for j in range(i+1,s_l):
        if s[i][0]==s[j][0]:
            if s[i]==s[j]:
                count+=1
print(count)

### FIXED CODE ###

N=int(input())
S = ["".join(sorted(input())) for _ in range(0, N)]
d={}
result=0
for s in S:
    if s in d.keys():
        result+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(result)
### BUGGY CODE ###

N = int(input())    
color_list =  [int(input())]
for i in range(N-1):
    new_value = int(input())
    if(new_value > color_list[0]):
        color_list[0] = new_value
    elif(new_value <= color_list[-1]):
        color_list.append(new_value)
    else:
        for i in range(len(color_list)):
            if(new_value > color_list[i]):
                color_list[i] = new_value
                break
print(len(color_list))

### FIXED CODE ###

def seek(value):
    right = len(color_list) - 1
    left = 0
    while(True):
        mid = (right + left) // 2
        if(value > color_list[mid]):
            right = mid
        else:
            left = mid
        if(right - left <= 1):
            return right

N = int(input())    
color_list =  [int(input())]
for i in range(N-1):
    new_value = int(input())
    if(new_value > color_list[0]):
        color_list[0] = new_value
    elif(new_value <= color_list[-1]):
        color_list.append(new_value)
    else:
        new_index = seek(new_value)
        color_list[new_index] = new_value
print(len(color_list))
### BUGGY CODE ###

# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H and dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
            elif i + a >= H and dp[i] + b < dp[H]:
                dp[H] = dp[i] + b
    print(dp[H])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


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

#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x)
#print(y)
F=0
S=0
for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1
if F<=S:
    print("Snuke")
else:
    print("Fennec")

### FIXED CODE ###

#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x)
#print(y)
F=0
S=0
for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1
if F<=S:
    print("Snuke")
else:
    print("Fennec")
### BUGGY CODE ###

S = input()
N = len(S)
S = list(S)
Children = [0]*N

RL = []
LR = []
for i in range(N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        RL.append(i+1)
    elif S[i] == 'L' and S[i+1] == 'R':
        LR.append(i+1)
LR.append(N)

Change = sorted(RL+LR)

Child = [LR[0]]
for i in range(1,len(LR)):
    Child.append(LR[i]-LR[i-1])

dig = [0]*len(Change)
dig[0] = Change[0]
for i in range(1,len(Change)):
    dig[i] = Change[i] - Change[i-1]

Rtype = [0]*len(RL)
for i in range(len(RL)):
    if Child[i] % 2 == 0:
        Rtype[i] = 0
    else:
        if dig[2*i]%2==0:
            Rtype[i] = 1
        if dig[2*i+1]%2==0:
            Rtype[i] = -1

k=0
for i in range(N):
    if i+1 in RL: #Rの方
        if Rtype[k] == -1:
            Children[i] += Child[k]//2 + 1
        else:
            Children[i] += Child[k]//2
    if i in RL: #Lの方
        if Rtype[k] == 1:
            Children[i] += Child[k]//2 + 1
        else:
            Children[i] += Child[k]//2
        k += 1

print(*Children)

### FIXED CODE ###

def ranlength(A):
    num = list(A)
    count = 1
    result = ''
    table = []
    for i in range(len(num)):
        try:
            if num[i] == num[i+1]:
               count = count + 1
            else:
                result += str(num[i]) + str(count)
                table.append(count)
                count = 1
        except:
            result += str(num[i]) + str(count)
            table.append(count)
    return(table)
    
S = ranlength(input())
#RRLRLなら[2,1,1,1]で出る

def gather(x,y):
    ans = [0]*(x+y)
    if (x+y)%2 == 0:
        ans[x-1] = (x+y)//2
        ans[x] = (x+y)//2
    if x%2 == 0 and y%2 != 0:
        ans[x-1] = (x+y)//2
        ans[x] = (x+y)//2 + 1
    elif x%2 != 0 and y%2 == 0:
        ans[x-1] = (x+y)//2 + 1
        ans[x] = (x+y)//2
    return(ans)

children = []
for i in range(len(S)//2):
    children += gather(S[2*i],S[2*i+1])

print(*children)
### BUGGY CODE ###

N = int(raw_input())
A = map(int, raw_input().split())

count = 0
for i in range(N):
	for j in range(i+1, N):
		if j - i == A[i] + A[j]:
			count += 1
print count

### FIXED CODE ###

N = int(raw_input())
A = map(int, raw_input().split())

x_occurance = {}
minus = []
for i in range(N):
	p = A[i] + i
	m = i - A[i]
	x_occurance[p] = x_occurance.get(p, 0) + 1
	minus.append(m)

count = 0
for i in range(N):
	count += x_occurance.get(minus[i], 0) 

print count
### BUGGY CODE ###

from numba import jit

def gcd(a,b):
    if b == 0: return a
    else: return gcd(b, a % b)

@jit
def main2(K):
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            for k in range(1,K+1):
                ans += gcd(gcd(i,j),k)
    return ans    


K = int(input())
print(main2(K))

### FIXED CODE ###

from numba import jit

@jit
def gcd(a,b):
    if b == 0: return a
    else: return gcd(b, a % b)

@jit
def main2(K):
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            tmp = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(tmp,k)
    return ans    


K = int(input())
print(main2(K))
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
m = 1
M = 0
i = 0
while M!=1:
    m = A[m-1]
    M = m
    i+=1

j = -1
K = k
while k>0:
    k = k-i
    j+=1

l = 0
while l != (K-i*j):
    m = A[m-1]
    l += 1

print(m)

### FIXED CODE ###

'''
path = 'sub1_51.txt'
f=open(path)
data1 = f.read()
f.close()
N=data1.split()
'''
n,k=map(int,input().split())
A=list(map(int,input().split()))
'''
n=int(N[0])
k=int(N[1])
A=N[2:]
'''
A=[int(i)-1 for i in A]
B=[]
cnt=[0]*n
m=0
for i in range(2*10**5):
    B.append(m)
    cnt[m]+=1
    if cnt[m]>1:
        break
    m=A[m]
c=len(B)-(B.index(m)+1)
print(1+B[(max(k-B.index(m),0))%c + min(B.index(m),k)])
#Bは街の移動順序
#cはループの長さ
### BUGGY CODE ###

from collections import defaultdict

"""
root = 10000
MODs = [10 ** 9 + 7, 10 ** 9 + 9]
def rolling_hash(s):
    hashes = [[0] * len(s) for _ in range(len(MODs))]
    for hs, MOD in zip(hashes, MODs):
        hs[0] = ord(s[0]) % MOD
        for i in range(1, len(hs)):
            hs[i] += hs[i - 1] * root + ord(s[i])
    return hashes        
"""

root = 10000
MOD = (1 << 61) - 1
def rolling_hash(s):
    hs = [0] * (len(s) + 1)
    for i in range(len(s)):
        hs[i + 1] = hs[i] * root + ord(s[i]) % MOD
    return hs

N = int(input())
S_list = [input() for _ in range(N)]
S_list.sort(key=len, reverse=True)

ans = 0
counts = defaultdict(int)
for S in S_list:
    alpha_suffix_set = set()
    hash_of_S = rolling_hash(S)
    alpha_set = set()
    for i in range(len(S)):
        alpha_set.add(S[i])
        suffix_hash = (hash_of_S[len(S)] - hash_of_S[i+1] * pow(root, (len(S) - i - 1), MOD)) % MOD
        for alpha in alpha_set:
            alpha_suffix_set.add((alpha, suffix_hash))

    suffix_of_S = (hash_of_S[len(S)] - hash_of_S[1] * pow(root, (len(S) - 1), MOD)) % MOD
    ans += counts[(S[0], suffix_of_S)]
    for elem in alpha_suffix_set:
        counts[elem] += 1
            
print(ans)


### FIXED CODE ###

from collections import defaultdict

root = 10000
MOD = 2 ** 61 - 1


#"""
N = int(input())
S_list = [input() for _ in range(N)]
"""
def to_alpha(n):
    ret = ''
    while n > 0:
        n -= 1
        ret += chr(n % 26 + ord('a'))
        n //= 26
    return ret

N = 2 * 10 ** 5
S_list = [to_alpha(i) for i in range(2, 2 * N + 2, 2)]
#"""


S_list.sort(key=len)

ans = 0
wanted = defaultdict(set)
for S in S_list:
    suffix_hashes = [0]
    for c in S[-1:0:-1]:
        suffix_hashes.append((suffix_hashes[-1] * root + ord(c)) % MOD)
    suffix_hashes.reverse()
    l = len(S)
    alpha_set = set()
    for i, c in enumerate(S):
        alpha_set.add(c)
        # print(alpha_set, suffix_hashes[i])
        if suffix_hashes[i] in wanted:
            for alpha in wanted[suffix_hashes[i]]:
                if alpha in alpha_set:
                    ans += 1
    wanted[suffix_hashes[0]].add(S[0])
        
# print(wanted)
print(ans)