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

def resolve():
	from collections import deque
	N, M, Q = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(Q)]
	
	def calc(x): # type(x) == str型
		ans = 0
		for a, b, c, d in A:
			if int(x[b-1]) - int(x[a-1]) == c:
				ans += d
		return ans
		
	q = deque([1])
	ans = 0
	while q:
		tmp = q.popleft()
		tmp = str(tmp)
		if len(tmp) == N:
			ans = max(ans, calc(tmp))
		else:
			for i in range(int(tmp[-1]), M+1):
				q.append(tmp+str(i))

	print(ans)
	
resolve()

### FIXED CODE ###

from collections import deque


# 数列の点数を計算する関数
def calc(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b - 1] - seq[a - 1] == c:
            score += d

    return score


n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]

ans = 0

que = deque()

# 数列の1番目、[1]～[m]までキューに追加しますが、
# 実は、この問題は数列の最初が[1]の場合だけを考えても解けます。
for i in range(1, m + 1):
    que.append([i])

while que:
    seq = que.popleft()

    if len(seq) == n:
        # 長さがnになったので、得点を計算します
        score = calc(seq)
        ans = max(ans, score)
    else:
        # 次に追加する数字は、下限が今の数列の一番後ろの数字、上限がmです
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            que.append(seq_next)

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

H, W = map(int, input().split())
M = [list(input().strip()) for _ in range(H)]
M_yoko = [[0 for _ in range(W)] for _ in range(H)]
M_tate = [[0 for _ in range(W)] for _ in range(H)]

for row in range(H):
    walls = [-1]
    for col in range(W):
        if M[row][col] == '#':
            walls.append(col)
    walls.append(W)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_yoko[row][j] = ed - st - 1

for col in range(W):
    walls = [-1]
    for row in range(H):
        if M[row][col] == '#':
            walls.append(row)
    walls.append(H)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_tate[j][col] = ed - st - 1

ans = 0
for row in range(H):
    for col in range(W):
        ans = max(ans, M_yoko[row][col] + M_tate[row][col])

print(ans-1)


### FIXED CODE ###

H, W = map(int, input().split())
M = [list(input().strip()) for _ in range(H)]
M_yoko = [[0 for _ in range(W)] for _ in range(H)]
M_tate = [[0 for _ in range(W)] for _ in range(H)]

for row in range(H):
    walls = [-1]
    for col in range(W):
        if M[row][col] == '#':
            walls.append(col)
    walls.append(W)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_yoko[row][j] = ed - st - 1

for col in range(W):
    walls = [-1]
    for row in range(H):
        if M[row][col] == '#':
            walls.append(row)
    walls.append(H)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_tate[j][col] = ed - st - 1

ans = 0
for row in range(H):
    for col in range(W):
        ans = max(ans, M_yoko[row][col] + M_tate[row][col])

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

N, M = map(int, input().split())
if M / N > 2:
    while True:
        M -= 2
        N += 1
        if M / N < 2:
            M += 2
            N -= 1
            break
    Scc = N
else:
    Scc = M // 2

print(str(Scc))

### FIXED CODE ###

N, M = map(int, input().split())
if M == 0:
    Scc = M // 4
elif M / N >= 2:
    M -= N * 2
    Scc = N + (M // 4)
else:
    Scc = M // 2

print(str(Scc))
### BUGGY CODE ###

n=int(input())
list1=list(map(int ,input().split()))
list2=[]
mod=1000000007
for i in range(n):
  for j in range(i+1,n):
    list2.append(list1[i]*list1[j]%mod)
a=sum(list2)%mod
    
print(a)
  

### FIXED CODE ###

n=int(input())
ans=0
mod=10**9+7
list1=list(map(int ,input().split()))
sums=sum(list1)

for i in list1:
  sums -=i
  ans +=sums*i%mod
  
print(ans%mod)
### BUGGY CODE ###

def Z_algo(S):
    n = len(S)
    LCP = [0] * n
    i = 1
    j = 0
    c = 0  # 最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        # i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i + LCP[i - c] < c + LCP[c]:
            LCP[i] = LCP[i - c]
        else:
            j = max(0, c + LCP[c] - i)
            while i + j < n and S[j] == S[i + j]:
                j += 1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP


n = int(input())
s = input()
ans = 0
for i in range(n):
    lcp = Z_algo(s[i:])
    for j in range(len(lcp)):
        tmp = min(j, lcp[j])
        ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

def Z_algo(S):
    n = len(S)
    LCP = [0] * n
    c = 0  # 最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        # i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i + LCP[i - c] < c + LCP[c]:
            LCP[i] = LCP[i - c]
        else:
            j = max(0, c + LCP[c] - i)
            while i + j < n and S[j] == S[i + j]:
                j += 1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP


n = int(input())
s = input()
ans = 0
for i in range(n):
    lcp = Z_algo(s[i:])
    for j, p in enumerate(lcp):
        tmp = min(j, p)
        ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

# input
N, M, K = map(int, input().split())

Frends = [[] for _ in range(N)]
Fs = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Frends[a].append(b)
    Frends[b].append(a)
    if a < b:
        Fs[a].append(b)
    else:
        Fs[b].append(a)

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].append(d)
    Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    l = Fs[i] 
    if len(l) == 0:
        continue

    l.append(i)
    s = set(l)

    t = -1
    j = 0
    fglen = len(fg)
    while j < fglen:
        sfg = s&fg[j]
        if len(sfg) > 0:
            if t < 0:
                t = j
                fg[j] |= s
            else:
                fg[t] |= fg[j]
                fg.pop(j)
                fglen -= 1
        j += 1

    if t < 0:
        fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for g in fg:
    for f in g:
        cand[f] = len(g)-len(Frends[f])-len(set(Blocked[f])&g)-1

# output
#print(fg)
print(" ".join(map(str, cand)))


### FIXED CODE ###

# input
N, M, K = map(int, input().split())

Friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Friends[a].add(b)
    Friends[b].add(a)

Blocked = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].add(d)
    Blocked[d].add(c)

# process
# 友人グループを作成
checked = set()
ans = [0]*N

for i in range (N):
    if i in checked:
        continue
    
    fg = set()

    stack = list(Friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue

        checked.add(f)
        fg.add(f)
        stack.extend(Friends[f])

    for f in fg:
        ans[f] += len(fg)-1-len(fg&(Friends[f]|Blocked[f]))

# output
print(" ".join(map(str, ans)))
### BUGGY CODE ###

from collections import defaultdict
N,M,*P = map(int,open(0).read().split())
d = defaultdict(list)
Z = set()
for n,m in zip(*[iter(P)]*2):
    d[n].append(m)
    Z.add(n)
for z in Z:
    d[z].sort()
for n,m in zip(*[iter(P)]*2):
    print(str(n).zfill(6)+str(d[n].index(m)+1).zfill(6))

### FIXED CODE ###

N,M = map(int,input().split())
P = []
Y = []
arr = [[]for j in range(10**5+1)]
for i in range(M):
  listA = list(map(int,input().split()))
  P.append(listA[0])
  Y.append(listA[1])
  arr[listA[0]].append(listA[1])
for i in range(N+1):
  arr[i].sort()
for i in range(M):
  #二部探索
  left = 0
  right = len(arr[P[i]])-1
  while left <= right:
    mid = (left+right)//2
    if arr[P[i]][mid] == Y[i]:
      k = mid
      break
    elif arr[P[i]][mid] > Y[i]:
      right = mid-1
    else:
      left = mid+1
  print(str(P[i]).rjust(6,'0')+str(k+1).rjust(6,'0'))
### BUGGY CODE ###

n,m=map(int,input().split())
marks = {i+1:-1 for i in range(n)}
roots = {i+1:[] for i in range(n)}
count = 0
for i in range(m):
    a,b = map(int,input().split())
    roots[a].append(b)
    roots[b].append(a)

before_room = 1
searchs = [{'root':roots[1], 'mark':1}]
while searchs != []:
    next_search = []
    for search in searchs:
        for root in search['root']:
            new_root = []
            if marks[root] == -1:
                marks[root] = search['mark']
                count += 1
                new_root += roots[root]
            next_search.append({'root':roots[root], 'mark':root})
    if count >= n-1:
        break
    searchs = next_search[:]

del marks[1]
print('Yes')
for v in marks.values():
    print(v)
    

### FIXED CODE ###

n,m=map(int,input().split())
marks = {i+1:-1 for i in range(n)}
marks[1] = 0
roots = {i+1:[] for i in range(n)}
count = 0
for i in range(m):
    a,b = map(int,input().split())
    roots[a].append(b)
    roots[b].append(a)

before_room = 1
searchs = [{'root':roots[1], 'mark':1}]
while searchs != []:
    next_search = []
    for search in searchs:
        for root in search['root']:
            new_root = []
            if marks[root] == -1:
                marks[root] = search['mark']
                count += 1
                new_root += roots[root]
            else:
                continue
            next_search.append({'root':roots[root], 'mark':root})
    searchs = next_search[:]

del marks[1]
print('Yes')
for v in marks.values():
    print(v)
### BUGGY CODE ###

from collections import Counter
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())

cnt = Counter()
for num in A:
    cnt[str(num)] += 1

values = sorted(cnt.values())
ans = 0
for x in xrange(len(values) - K):
    ans += values.pop(0)

print ans

### FIXED CODE ###

from collections import Counter
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())

cnt = Counter()
for num in A:
    cnt[str(num)] += 1

values = sorted(cnt.values())
ans = sum(values[:max(len(values)-K, 0)])

print ans
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    from functools import lru_cache

    @lru_cache(None)
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)
    
    ta = 0
    for k,v in c.items():
        if v >= 2:
            ta += combination(v, 2)
            
    # dp = [-1] * (N+1)
    ans = []
    for i in range(N):
        t = ta
        if c[A[i]] >= 2:
            t -= combination(c[A[i]], 2)
        if c[A[i]]-1 >= 2:
            t += combination(c[A[i]]-1, 2)    
        ans.append(t)

 
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    from functools import lru_cache

    @lru_cache(None)
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)
    
    ta = 0
    for k,v in c.items():
        if v >= 2:
            ta += combination(v, 2)
            
    # dp = [-1] * (N+1)
    ans = []
    for i in range(N):
        t = ta
        if c[A[i]] >= 2:
            t -= combination(c[A[i]], 2)
        if c[A[i]]-1 >= 2:
            t += combination(c[A[i]]-1, 2)
        
        ans.append(t)

 
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import math
k = int(input())
ans = 0
for q in range(1,k+1):
    for r in range(1,k+1):
        for s in range(1,k+1):
            ans += math.gcd(q,math.gcd(r,s))

print(ans)


### FIXED CODE ###

import math
k = int(input())
ans = 0
for q in range(1,k+1):
    for r in range(1,k+1):
        x = math.gcd(q,r)
        for s in range(1,k+1):
            ans += math.gcd(x,s)

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

n = int(input())
m = 0

for i in range(n):
	if i == n:
		pass
	else:
		m += i

print(m)

### FIXED CODE ###

n = int(input())
ans = 0

if n == 2:
    ans = 1
elif n % 2 != 0:
    ans = n * (n // 2)
else:
    ans = n * (n // 2 - 1) + n // 2

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

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
e=q.append
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   e(t);d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
for i in range(1,X+1):
    O[i]=2*O[i-1]
for i in range(X):
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]%b+b)%b
    else:
        b=d+1
        flag=1
        g=(e+O[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

### FIXED CODE ###

from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
P=[1]*(X+2)
q=max(d-1,1)
for i in range(1,X+1):
    O[i]=O[i-1]*2%q
    P[i]=P[i-1]*2%(d+1)
for i in range(X):
    
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]+b)%b
    else:
        b=d+1
        flag=1
        g=(e+P[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)
### BUGGY CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    #idx = bisect.bisect_left(A, pow(A[i],0.5))
    #J = min(idx+1,i)
    J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)



### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0:
        for i in range(10**7):
            x = a*i
            if x>10**6:
                break
            P[x] = 1
        if cnt[a]==1:
            ans +=1

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

import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[{} for _ in range(n)]
c,p=map(int,input().split())
dp[0][c]=p
 
def ans(n,w):
  for i in range(1,n):
    c,p=map(int,input().split())
    for j in dp[i-1].keys():
      dp[i][j]=dp[i-1][j]
    for j in dp[i-1].keys():
      tmp=dp[i-1][j]+p
      if j+c <= w:
        if j+c in dp[i-1]:
          dp[i][j+c]=max(dp[i-1][j+c],tmp)
        else:
          dp[i][j+c]=tmp
    if c in dp[i-1]:
      dp[i][c]=max(dp[i-1][c],p)
    else:
      dp[i][c]=p
  return max([dp[n-1][i] for i in dp[n-1].keys()])
print(ans(n,w))

### FIXED CODE ###

n,w=map(int,input().split())
dp=[0]*(n*10**3+1)
c,p=map(int,input().split())
dp[p]=c
mpos=p
for _ in range(n-1):
  c,p=map(int,input().split())
  for i in range(mpos+p,0,-1):
    if dp[i-p]!=0:
      if dp[i]==0:
        dp[i]=dp[i-p]+c
      else:
        dp[i]=min(dp[i-p]+c,dp[i])
  if dp[p]==0:
    dp[p]=c
  else:
    dp[p]=min(dp[p],c)
  mpos=mpos+p
ans=0
for i in range(len(dp)):
  if dp[i]<=w and dp[i]!=0:
    ans=i
print(ans)
### BUGGY CODE ###

n = int(input())
possible = [1]
i=1
while i <= 100000:
  i = i*6
  possible+=[i]
i=1
while i <= 100000:
  i = i*9
  possible+=[i]
possible.sort(reverse =1)
ans = 1
table = set(possible)
while True:
  if n in table:
    print(ans)
    break
  ans+=1
  nexttable = set()
  for num in table:
    for p in possible:
      if num + p <100000:
        nexttable.add(num+p)
  table = table | nexttable

### FIXED CODE ###

n = int(input())
possible = [1]
i=1
while i <= 100000:
  i = i*6
  possible+=[i]
i=1
while i <= 100000:
  i = i*9
  possible+=[i]
possible.sort(reverse =1)
ans = 0
table = set([n])
while True:
  if 0 in table:
    print(ans)
    break
  ans+=1
  nexttable = set()
  for num in table:
    for p in possible:
      if num - p >= 0:
        nexttable.add(num-p)
  table =nexttable
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
negative_A = - np.array(A)

gu_idx = [i for i in range(N) if i % 2 == 0]
ki_idx = [i for i in range(N) if i % 2 == 1]

ans = []
for idx, dam in enumerate(A):
#     print(A[gu_idx])
    ans.append(str(sum(A[gu_idx]) + sum(negative_A[ki_idx])))
    
    A = np.roll(A, -1)
    negative_A = np.roll(negative_A, -1)       
    
print(" ".join(ans))

### FIXED CODE ###

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

irekae_sum = 0
for idx, a in enumerate(A):
    if idx % 2 == 0:    
        irekae_sum += a
    else:
        irekae_sum -= a
        
ans = []
for i in range(N):
    ans.append(str(irekae_sum))
    irekae_sum = - irekae_sum + 2*A[i]
            
print(" ".join(ans))
### BUGGY CODE ###

N = int(input())

memo = []
for i in range(N):
  A = int(input())
  if(A not in memo):
    memo.append(A)
  else:
    memo.remove(A)
print(len(memo))

### FIXED CODE ###

N = int(input())
A = [input() for _ in range(N)]

memo = {}
for a in A:
  if(a not in memo):
    memo[a] = 0
  else:
    memo.pop(a)
print(len(memo))
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
l = len(a)
for i in range(l-1):
    for j in range(i,l):
        if a[i]!=a[j]:
            ans += ( a[i]^a[j] ) % mod
print(ans%mod)

### FIXED CODE ###

import math
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def myinput():
    return map(int,readline().split())

n = int(readline())
a = list(myinput())
mod = 10**9 + 7
ans = 0

for j in range(60):
    k = 2**j
    one = 0
    zero = 0
    for i in range(n):
        if (a[i]&k):
            one += 1
        else:
            zero += 1
    ans_bit = zero * one
    ans += (ans_bit)*(2**j) 
    ans %= mod   

print(ans%mod)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(w1, w2):
    m, n = len(w1), len(w2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_l = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            max_l = max(max_l, dp[i][j])

    return max_l


def solve():
    input_ = sys.stdin.readlines()
    pair_num = int(input_[0])

    word_list = input_[1:]
    # assert len(word_list) == 2 * pair_num

    for pair in zip(word_list[::2], word_list[1::2]):
        cw1, cw2 = map(lambda x: x.strip(), pair)
        print(lcs(cw1, cw2))
        # l1, l2 = len(cw1), len(cw2)
        # print(lcs_recursive(cw1, cw2, l1, l2))

    return


if __name__ == '__main__':
    solve()

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

from collections import Counter
import itertools

def verify_anagrams(first_word, second_word):
    return Counter(first_word) == Counter(second_word)

N = int(input())
S = []
for _ in range(N):
    S.append(Counter(input()))
sum = 0

x = itertools.combinations(S, 2)
for combi in x:
    if combi[0] == combi[1]:
        sum += 1
# print(Counter(S))
print(sum)

### FIXED CODE ###

from collections import Counter
import itertools

N = int(input())
S = ["".join(sorted(input())) for _ in range(N)]
print(sum((x * (x - 1)) // 2 for x in Counter(S).values()))
### BUGGY CODE ###

L,R = map(int, input().split())
 
ans = 2019
for i in range(L,R):
  for j in range(i + 1,R + 1):
    aa = i * j
    aaa = aa % 2019
    
    if aaa < ans:
      ans = aaa
    
    if ans == 0:
      break
      
print(ans)

### FIXED CODE ###

L,R = map(int, input().split())

if R - L >= 2019:
  print(0)
else:
  ans = 2019
  for i in range(L,R):
    for j in range(i + 1,R + 1):
      aa = i * j
      aaa = aa % 2019
    
      if aaa < ans:
        ans = aaa
    
      if ans == 0:
        break
      
  print(ans)
### BUGGY CODE ###

from collections import Counter

n=int(input())
l=list(map(int,input().split()))

cl=Counter(l)

for i in range(n):
  if i==0:
    num=0
    cl[l[i]]-=1
    for j in cl.values():
      num+=(j*(j-1)/2)
  else:
    cl[l[i]]-=1
    cl[l[i-1]]+=1
    num=0
    for j in cl.values():
      num+=(j*(j-1)/2)
  print(int(num))
  

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 22:04:16 2020

@author: liang
"""

N = int(input())
A = [int(x) for x in input().split()]
d = [0]*N

for a in A:
    d[a-1] += 1
#print(d)
score = 0
for  a in d:
    score += a*(a-1)//2
#print(score)
for a in A:
    print(score - d[a-1] + 1)