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

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

import collections

dct=collections.Counter(lst)


for i in range(N):
    total={}
    for k, v in dct.items():
        total[k]=v*(v-1)//2
Sum=sum(total.values())


for i in range(N):
    print(Sum-dct[lst[i]]+1)

### FIXED CODE ###

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

import collections

dct=collections.Counter(lst)


#for i in range(N):
Sum=0
for v in dct.values():
        Sum+=v*(v-1)//2


for i in range(N):
    print(Sum-dct[lst[i]]+1)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    A, B, C, K = map(int, open(0).read().split())

    flag = True
    for i in range(0, K):
        if abs(A - B) > 10**18:
            print('Unfair')
            flag = False
            break
        elif A == B == C:
            print(0)
            flag = False
            break
        else:
            tmpA = B + C
            tmpB = A + C
            tmpC = A + B
            A = tmpA
            B = tmpB
            C = tmpC
    if flag:
        print(A - B)


main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    A, B, C, K = map(int, open(0).read().split())

    if abs(A - B) > 10**18:
        print('Unfair')
    else:
        if K % 2:
            print(B - A)
        else:
            print(A - B)


main()
### BUGGY CODE ###

import sys
from collections import Counter
from random import sample

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

N = INT()
A = LIST()
B = LIST()

C1 = Counter(A)
C2 = Counter(B)
for k, v in C1.items():
    if v > N-C2[k]:
        No()
        exit()

ans = B[ceil(N, 2):] + B[:ceil(N, 2)]

def check(A, B):
    for i in range(N):
        if A[i] == B[i]:
            return i
    return -1

def swap(x, A, B):
    for i in sample([a for a in range(N)], N):
        if A[x] != B[i] and A[i] != B[x]:
            B[x], B[i] = B[i], B[x]
            return True
    return False

while 1:
    res = check(A, ans)
    if res == -1:
        Yes()
        print(*ans)
        break
    else:
        if not swap(res, A, ans):
            No()
            break


### FIXED CODE ###

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

N = INT()
A = LIST()
B = LIST()

C1 = Counter(A)
C2 = Counter(B)
for k, v in C1.items():
    if v > N-C2[k]:
        No()
        exit()

ans = B[ceil(N, 2):] + B[:ceil(N, 2)]

def check(A, B):
    for i in range(N):
        if A[i] == B[i]:
            return i
    return -1

def swap(x, A, B):
    for i in range(N):
        if A[x] != B[i] and A[i] != B[x]:
            B[x], B[i] = B[i], B[x]
            return True
    return False

while 1:
    res = check(A, ans)
    if res == -1:
        Yes()
        print(*ans)
        break
    else:
        if not swap(res, A, ans):
            No()
            break
### BUGGY CODE ###

s = list(input())

cnt = 0
# print(s, cnt)

i = 0
while i < len(s)-2:
    # print(i)
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        s[i] = 'B'
        s[i+1] = 'C'
        s[i+2] = 'A'
        cnt = cnt + 1
        i = i - 1
        if i < 0:
            i = 0
        # print(i, s, cnt)
    else:
        i = i + 1

print(cnt)

### FIXED CODE ###

s = input()
t = s.replace('BC', 'D')

a = 0 # 連続するaの数
ans = 0 # 答え

for i in t:
    if i == 'A':
        a += 1
    elif i == 'D':
        ans += a
    else:
        a = 0

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

import sys
sys.setrecursionlimit(10**6)
def bknap(curw,wei,val,n):
 if(n==0 or curw==0):
  return 0
 if(wei[n-1]>curw):
  return bknap(curw,wei,val,n-1)
 else:
  return max(val[n-1]+bknap(curw-wei[n-1],wei,val,n-1),bknap(curw,wei,val,n-1))
n,w=map(int,input().split())
wei=[]
val=[]
for i in range(n):
 w1,v1=map(int,input().split())
 wei.append(w1)
 val.append(v1)
print(bknap(w,wei,val,n))

  


### FIXED CODE ###

import sys
input=sys.stdin.readline
def fun(n,w):
 cos=[0]*(w+1)
 for i in range(n):
  w1,v1=map(int,input().split())
  for j in range(w,w1-1,-1):
   f=cos[j-w1]+v1
   if(cos[j]<f):
    cos[j]=f
 print(cos[-1])
n,w=map(int,input().split())
fun(n,w)
### BUGGY CODE ###

lst=list(map(int,input().split()))
lst[1]/=1000

i=0
for a in range(lst[0]+1):
    if i !=0:
        break
    for b in range(lst[0]+1):
        if i !=0:
            break
        for c in range(lst[0]+1):
            if a+b+c==lst[0]:
                if 10*a+5*b+c==lst[1]:
                    print(a,b,c)
                    i=1
                    break
if i==0:
    print(-1,-1,-1)


### FIXED CODE ###

lst=list(map(int,input().split()))
lst[1]/=1000
i=0
for a in range(lst[0]+1):
    if i !=0:
        break
    for b in range(lst[0]+1):
     	if lst[0]-a-b>=0:
            if 10*a+5*b+(lst[0]-a-b)==lst[1]:
                print(a,b,lst[0]-a-b)
                i=1
                break
        
if i==0:
    print(-1,-1,-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = []
m = 1

def f(m, a):
    s_tmp = 0
    for i in range(n):
        s_tmp = s_tmp + m % a[i]
    return s_tmp

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

for i in range(1,m):
    s.append(f(i, a))

print(max(s))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = []
m = 1

def f(m, a):
    s_tmp = 0
    for i in range(n):
        s_tmp = s_tmp + m % a[i]
    return s_tmp

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

print(f(m-1, a))
### BUGGY CODE ###

n = input()
dic = []
for i in xrange(n):
    order = raw_input().split()
    if order[0][0] == 'i':
        dic.append(order[1])
    else:
        print "yes" if order[1] in dic else "no"

### FIXED CODE ###

n = input()
dic = set([])
for i in xrange(n):
    order = raw_input().split()
    if order[0][0] == 'i':
        dic.add(order[1])
    else:
        print "yes" if order[1] in dic else "no"
### BUGGY CODE ###

import sys
from collections import Counter
 
inf = 1<<60
 
def solve():
    N, M = map(int, input().split())
    edges = [None]*M
 
    for i in range(M):
        ui, vi, ci = map(int, sys.stdin.readline().split())
        edges[i] = (ui-1, vi-1, -ci)
 
    ans = Bellmanford(N, M, edges)
 
    if ans is not None:
        print(-ans)
    else:
        print('inf')
 
def Bellmanford(N, M, edges):
    dist = [inf]*N
    dist[0] = 0
    flag = True
 
    while True:
        flag = False
 
        for (u, v, c) in edges:
            if dist[u] != inf and dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                flag = True
 
        # print(dist)
 
        if not flag or dist[0] < 0:
            break
 
    if dist[0] >= 0:
        return dist[N - 1]
    else:
        return None
 
if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
from collections import Counter

sys.setrecursionlimit(10**7)
 
inf = 1<<100
 
def solve():
    N, M = map(int, input().split())
    edges = [None]*M
    Adj = [[] for i in range(N)]
 
    for i in range(M):
        ui, vi, ci = map(int, sys.stdin.readline().split())
        ui, vi = ui - 1, vi - 1
        edges[i] = (ui, vi, -ci)
        Adj[ui].append(vi)

    visitable = [False]*N

    dfs(N, M, Adj, visitable, 0)

    reachable = [False]*N
    reachable[0] = True
    reachable[N - 1] = True

    for u in range(1, N - 1):
        visited = [False]*N

        dfs(N, M, Adj, visited, u)

        if visited[N - 1]:
            reachable[u] = True
 
    ans = Bellmanford(N, M, edges, visitable, reachable)
 
    if ans is not None:
        print(-ans)
    else:
        print('inf')

def dfs(N, M, Adj, visitable, u):
    visitable[u] = True

    for v in Adj[u]:
        if not visitable[v]:
            dfs(N, M, Adj, visitable, v)

def Bellmanford(N, M, edges, visitable, reachable):
    dist = [inf]*N
    dist[0] = 0
    flag = True

    cnt = 0
 
    for i in range(N):
        flag = False

        for (u, v, c) in edges:
            if dist[u] != inf and dist[v] > dist[u] + c:
                dist[v] = dist[u] + c

                if visitable[v] and reachable[v]:
                    flag = True

        # print(dist)

        if not flag:
            break

        if flag and i == N - 1:
            return None

    return dist[N - 1]
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

N=int(input())
A_list=list(map(int,input().split()))
ans=1
for i in range(N):
    ans=ans*A_list[i]

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

### FIXED CODE ###

N=int(input())
A_list=list(map(int,input().split()))
ans=1
for i in range(N):
    ans=ans*A_list[i]
    if ans>10**18:
        ans=-1
        break 
for i in A_list:
    if i==0:
        ans=0
print(ans)
### BUGGY CODE ###

def solve():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pd = {i: x for i, x in enumerate(p, 1)}
    cd = {i: x for i, x in enumerate(c, 1)}
    ans = -10 ** 10
    for i in range(1, n + 1):
        res = 0
        x = i
        for j in range(1, k + 1):
            res += cd[x]
            x = pd[x]
            ans = max(res, ans)
    print(ans)


solve()


### FIXED CODE ###

def solve():
    from collections import defaultdict
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.par = [-1] * n

        def find(self, x):
            if self.par[x] < 0:
                return x
            else:
                self.par[x] = self.find(self.par[x])
                return self.par[x]

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.par[x] > self.par[y]:
                x, y = y, x

            self.par[x] += self.par[y]
            self.par[y] = x

        def size(self, x):
            return -self.par[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    mp = defaultdict(int)
    uf = UnionFind(n)

    for i in range(n):
        uf.unite(i, p[i] - 1)

    for i in range(n):
        mp[uf.find(i)] += c[i]

    ans = -10 ** 14
    for i in range(n):
        roop = uf.size(i)
        times = (k - 1) // roop if mp[uf.find(i)] > 0 else 0
        over = max(min(roop, k - roop * times), 1)
        tmp = 0
        s = -10 ** 10
        idx = i
        for j in range(over):
            tmp += c[idx]
            s = max(s, tmp)
            idx = p[idx] - 1
        s += times * mp[uf.find(i)]
        ans = max(ans, s)
    print(ans)


solve()
### BUGGY CODE ###

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

INF = 10**9
dp = [INF]*N

for i in range(len(A)):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(A[1]-A[0])
    else:
        jmp = min(i,K)
        for j in range(1,jmp+1):
            dp[i] = min(dp[i], dp[i-j]+abs(A[i]-A[i-j]))
            
print(dp[N-1])

### FIXED CODE ###

def main():
    N,K=map(int, input().split())
    A = list(map(int, input().split()))

    dp = [float('inf')] * N
    dp[0] = 0
    for i in range(1,len(A)):
        jmp = max(0,i-K)
        dp[i] = min([dp[j]+abs(A[i]-A[j]) for j in range(jmp, i)])
    print(dp[N-1])

main()
### BUGGY CODE ###

def m():
    N = int(input())
    X = [int(x) for x in input().split()]
    for x in range(N):
        XX = [x for x in X]
        XX[x] = -1
        XX.sort()
        print(XX[N//2])


m()


### FIXED CODE ###

def m():
    N = int(input())
    X = [int(x) for x in input().split()]
    XX = [x for x in X]
    XX.sort()
    first = XX[N//2]
    second = XX[N//2 -1]
    for x in range(N):
        if X[x] <= second:
            print(first)
        else:
            print(second)


m()
### BUGGY CODE ###

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

N=int(input())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=cmb(N,3)
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if (L[i]+L[j])<=L[k]:
                ans-=(N-k)
                break


print(int(ans))

### FIXED CODE ###

from operator import mul
from functools import reduce
import bisect

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

N=int(input())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=cmb(N,3)
ans2=0
for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        a=bisect.bisect_right(L,L[i]-L[j])
#        print('{0}:{1}'.format(a,j))
#        print(a)
        if(a<j):
            ans2+=(j-a)
    

print(ans2)
### BUGGY CODE ###

N = int(input())
Y = []
for i in range(N):
    S = input()
    if S not in Y:
        Y.append(S)
print(len(Y))

### FIXED CODE ###

N = int(input())
Y = []
for i in range(N):
    Y.append(input())
print(len(set(Y)))
### BUGGY CODE ###

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


f = []

for i in range(n + 1):
    if i == 0:
        f.append(1)
        continue
    if i in a:
        f.append(0)
        continue
    if i == 1:
        f.append(1)
        continue
    f.append(f[i - 1] + f[i - 2])
    
print(f[n] % 1000000007)


### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
NUM = 10 ** 9 + 7

dp = [0] * (n+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1

for i in range(2, n+1):
    if not i in a:
        dp[i] = (dp[i-2] + dp[i-1]) % NUM
    else:
        dp[i] = 0

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

# coding: utf-8
# Your code here!

INPUT=int(input())
b=1
p=2
END=0
while True:
    while True:
        now_num = b**p
        if b == 1:
            end_num=now_num
            break
        elif p==2 and INPUT<now_num:
            END = 1
            break
        elif INPUT < now_num:
            end_num = b**(p-1)
            break
        else:
            p+=1
        
    if END == 1:
        ans=end_num
        break
    b+=1
    
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

from math import sqrt
X=int(input())
sqrt_X=int(sqrt(X))
ans=1

for b in range(sqrt_X):
    for p in range(sqrt_X - 1):
        now_num = (b+1)**(p+2)
        if now_num <= X and ans <= now_num:
            ans =now_num
print(ans)
### BUGGY CODE ###

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

b = 1
for j in range(K):
    b *= A[j]

for i in range(1, N-K+1):
    a = b // A[i-1]
    a *= A[i+K - 1]
    print('Yes' if a > b else 'No')
    b = a




### FIXED CODE ###

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

for i in range(1, N-K+1):
    print('Yes' if A[i - 1] < A[i+K - 1] else 'No')
### BUGGY CODE ###

n=int(input())
S=[input() for i in range(n) ]
L=sorted(set(S))
cnt=[]
for l in L:
    cnt.append(S.count(l))
op=[L[i] for i, x in enumerate(cnt) if x == max(cnt)]
print("\n".join(op))


### 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_N = max(list(dic.values()))
keys = sorted([k for k, v in dic.items() if v == max_N])

print("\n".join(keys))
### BUGGY CODE ###

n,k,q = map(int,input().split())
correctAnswer = [0 for i in range(q)]
participant = [k for i in range(n)]


for i in range(q): # q = 正解者のかず
	correctAnswer[i] = int(input())

for correct in correctAnswer:
	for i in range(n):# n = 参加者の人数
		participant[i] -= 1 
	participant[correct-1] += 1



for i in range(n):
	if participant[i] <= 0:
		print('No')
	else:
		print('Yes')


### FIXED CODE ###

n,k,q = map(int,input().split())
participant = [k-q for i in range(n)]


for i in range(q):# q = len.correctAnswer
	participant[int(input())-1] += 1

for i in participant :
	if i <= 0:
		print('No')
	else:
		print('Yes')
### BUGGY CODE ###

# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H =defaultdict(int)
bom_W =defaultdict(int)
posision =defaultdict(int)
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision[(h,w)] =1
max_H = [kv for kv in bom_H.items() if kv[1] == max(bom_H.values())]
max_W = [kv for kv in bom_W.items() if kv[1] == max(bom_W.values())]
temp_H =max_H[0][1]
temp_W =max_W[0][1]

ans =temp_H +temp_W -1
for p_h,v_h in max_H:
    for p_w,v_w in max_W:
        if posision[(p_h,p_w)] ==0:
            ans =v_h +v_w 
            print(ans)
            sys.exit()

print(ans)

### FIXED CODE ###

import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
        # 即座に探索を終了する.
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(max(A))
r=1
for a in A:
    p2=p.copy()
    for x in p:
        if a%x==0:
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        r=0
        break
    p=p2
print(['setwise coprime','pairwise coprime'][r])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(1000)
r=1
s=set()
for a in A:
    f=0
    for x in p:
        if a%x==0:
            if f==0:
                p2=p.copy()
                f=1
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        if 1000<a and a not in s:
            s.add(a)
        else:
            r=0
            break
    if f:
        p=p2
print(['setwise coprime','pairwise coprime'][r])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for i in range(int(b/a), n+1):
  ans = max(ans, int(a*i/b)-a*int(i/b))
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
ans = 0
e = min(n+1,b)
s = max(int(b/a),e-1000)
for i in range(s, e):
  x = (int(a*i/b)-a*int(i/b))
  if ans < x:
    ans = x
print(ans)