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

X, Y, Z, K = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

ablst = [m + n for n in b for m in a]

ablst.sort(reverse=True)

abclst = [m + n for m in ablst[:K] for n in c]

abclst.sort(reverse=True)

print(*abclst[:K], sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)

ablst = [m + n for n in b for m in a]

ablst.sort(reverse=True)

c.sort(reverse=True)

abclst = [m + n for n in c[:K] for m in ablst[:K]]

abclst.sort(reverse=True)

print(*abclst[:K], sep='\n')
### BUGGY CODE ###

import sys

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

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

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

debug = False

if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()




# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

    for i in range(60):
        ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

    # a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans//2 % MOD)


### FIXED CODE ###

import sys
import time

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

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

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

start = time.time()

MOD = 10**9+7

debug = False

if debug:
    n = 30 * 10000
    A = list(range(n))
else:
    n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)
# log("bits.", time.time() - start)

# ans = 0

ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

# for a in A:
#     # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

#     for i in range(60):
#         ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

#     # a_dash = list(map(lambda a: a*(n-1), a_bits))

#     # log("a_dash", a_dash)

#     # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
#     # log("bits_dash", bits_dash)
#     # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

#     # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

#     # for i in range(60):
#     #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
#     # log(a, ans)

# print(ans//2 % MOD)
print(ans)
# log("end.", time.time() - start)
### BUGGY CODE ###

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

ans = 0
for i in range(B+1):
    if i > N:
        break
    n = (A * i // B) - A * (i // B)
    ans = max(ans, n)

print(ans)




### FIXED CODE ###

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

x = min(B-1, N)

ans = (A * x // B) - A * (x // B)

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

n, k = map(int, input().split())
s = list(map(int, input().split()))
# s.sort()
if k > len(s):
    k = len(s)
for j in range(1, k+1):
    s[s.index(max(s))] = 0
print(sum(s))


### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int, input().split()))
if k > len(s):
    k = len(s)
s = sorted(s, reverse=True)

print(sum(s[k:]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
count=0
for i in a:
  for j in b:
    for k in c:
      if i<j<k:
        count=count+1
print(count)
        

### FIXED CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
A = 0
for x in b:
  i = bisect.bisect_left(a, x)
  j = bisect.bisect_right(c, x)
  if i > 0 and j != len(c):
    A += i * (n - j)
print(A)
### BUGGY CODE ###

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

top = 0
for i in range(M):
  for j in range(len(A)):
    if A[j] > A[top]:
      top = j
  A[top] = A[top] // 2

print(sum(A))

### FIXED CODE ###

import heapq
import math

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

hq = []
for a in A:
  heapq.heappush(hq, a * -1)

for i in range(M):
  n = math.ceil(heapq.heappop(hq) / 2)
  heapq.heappush(hq, n)

b = []
for hqi in hq:
  b.append(hqi * -1)
  
print(sum(b))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
X, Y = [], []
for i in range(N):
    X.append(i + 1 + A[i])
    Y.append(i + 1 - A[i])
X.sort()
Y.sort()
c = 0
for i in range(N):
    if X[i] > Y[-1]:
        break
    for j in range(N):
        if X[i] == Y[j]:
            c += 1
        if X[i] < Y[j]:
            break
print(c)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
X, Y = [], []
for i in range(N):
    X.append(i + 1 + A[i])
    Y.append(i + 1 - A[i])
XL = Counter(X)
c = 0
for y in Y:
    c += XL.get(y, 0)
print(c)
### BUGGY CODE ###

#!/usr/bin/env python

import sys

def getVertex(i,e):
    v= set()
    for v1 in e[i]:
        for v2 in e[v1]:
            for v3 in e[v2]: v.add( v3 )
    #
    return v
#
n,m = [ int(x) for x in sys.stdin.readline().split() ]
e = { i:[] for i in range(n) }
for _ in range(m):
    u,v = [ int(x) for x in sys.stdin.readline().split() ]
    e[u-1].append( v-1 )
s,t = [ int(x)-1 for x in sys.stdin.readline().split() ]
#
kkp= { i:[] for i in range(n) }
#
hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
    #
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
    visit|= n
#
print( hop )


### FIXED CODE ###

#!/usr/bin/env python

import sys

v1mask= set()
v2mask= set()

def getVertex(i,e):
    global v1mask, v2mask
    v= set()
    for v1 in e[i]:
        if v1 in v1mask: continue
        v1mask.add( v1 )
        for v2 in e[v1]:
            if v2 in v2mask: continue
            v2mask.add( v2 )
            for v3 in e[v2]: v.add( v3 )
    #
    return v
#
n,m = [ int(x) for x in sys.stdin.readline().split() ]
e = { i:[] for i in range(n) }
for _ in range(m):
    u,v = [ int(x) for x in sys.stdin.readline().split() ]
    e[u-1].append( v-1 )
s,t = [ int(x)-1 for x in sys.stdin.readline().split() ]
#
hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
        if t in n: break
    #
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
    visit|= n
#
print( hop )
### BUGGY CODE ###

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


### FIXED CODE ###

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

a = input()
a = int(a)
sum = 0
for i in range(1,a+1):
  for j in range(1,a+1):
    for k in range(1,a+1):
      for b in range(a,0,-1):
        if i%b==0 and j%b==0 and k%b==0:
          sum += b
          break
print(sum)

### FIXED CODE ###

import math
K = int(input())
sum = 0
for i in range(1, K+1):
  for j in range(i, K+1):
    #2i or 3i
    if (i == j):
      for k in range(i, K+1):
        #print("i"+str(i)+"j"+str(j)+"k"+str(k))
        if ((i == j) and (i == k)):
          sum += math.gcd(i, math.gcd(j, k))
        else:
          sum += (3*math.gcd(i, math.gcd(j, k)))
    #1i
    else:
      for k in range(i+1, K+1):
        #print("i"+str(i)+"j"+str(j)+"k"+str(k))
        sum += (3*math.gcd(i, math.gcd(j, k)))
      
print(sum)
### BUGGY CODE ###

def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		M = max([A, B])
		m = min([A, B])
		route[m - 1] += [M]
		route[M - 1] += [m]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		if checked[src - 1] == 0:
			checked[src - 1] = 1
			signal[src - 1] = checking["dst"]
			rooms = route[src - 1]
			for r in rooms:
				to_check.append({"src": r, "dst": src})
	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join([str(q) for q in signal[1:]]))

main()

### FIXED CODE ###

def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		route[A - 1] += [B]
		route[B - 1] += [A]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	for r in route[0]:
		checked[r - 1] = 1

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		signal[src - 1] = str(checking["dst"])
		rooms = route[src - 1]
		for r in rooms:
			if checked[r - 1] == 0:
				to_check.append({"src": r, "dst": src})
				checked[r - 1] = 1

	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join(signal[1:]))

main()
### BUGGY CODE ###

def main():
    """"ここに今までのコード"""
import numpy as np
n = int(input())
A=list(map(int, input().split()))


bit= np.array([[0]*60 for i in range(n)])
for i in range(n):
    a=A[i]
    j=1
    if a!=0:    
        while a//2>0:
            if a%2==1:
                bit[i][60-j]=1
                j+=1
                a=a//2
            else:
                j+=1
                a=a//2
        bit[i][60-j]=1
           
l=np.sum(bit,axis=0)           
xor=([n]*60-l)*l
    
#for j in range(60):
    #for i in range(n):
        #l+=bit[i][j]
    #xor[j]=l*(n-l)
    
L=10**9+7
ans=xor[0]
for j in range(60-1):
    ans=((2*ans)+xor[j+1])%L
print(ans) 

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
 
n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7
 
ans=0
for i in range(60):
    l=sum([a%2 for a in A])
    ans=(ans+l*(n-l)*(2**i))%mod
    A=[a//2 for a in A]
    
 
#ans=xor[0]
#for j in range(60-1):
#    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = [[X[k],k] for k in range(N)]
Z = sorted(Y)
A = [0 for k in range(N)]

for k in range(N):
    A[Z[k][1]] = (Z[:Y[k][1]]+Z[Y[k][1]+1:])[N//2-1][0]

for x in A:
    print(x)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = [[X[k],k] for k in range(N)]
Y.sort()
A = [0 for k in range(N)]

for k in range(N):
    if k >= N//2:
        A[Y[k][1]] = Y[N//2-1][0]
    else:
        A[Y[k][1]] = Y[N//2][0]

for x in A:
    print(x)
### BUGGY CODE ###

N = input()
S = input()
ans = set()
for i in range(len(S)-2):
    for j in range(i+1, len(S)-1):
        for k in range(j+1, len(S)):
            s = S[i]+S[j]+S[k]
            if s not in ans:
                ans.add(s)
print(len(ans))


### FIXED CODE ###

N = input()
S = list(input())
count = 0
num_count = [False]*10
for i in range(len(S)-2):
    s_i = int(S[i])
    if num_count[s_i]:
        continue
    num_count[s_i] = True
    num_count_2 = [False]*10
    for j in range(i+1, len(S)-1):
        s_j = int(S[j])
        if num_count_2[s_j]:
            continue
        num_count_2[s_j] = True
        num_count_3 = [False] * 10
        for k in range(j+1, len(S)):
            s_k = int(S[k])
            if num_count_3[s_k]:
                continue
            num_count_3[s_k] = True
            count += 1
print(count)
### BUGGY CODE ###

def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out#int outn=int(input())
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
n=int(input())
x=input()
ans=[]
pc=x.count("1")
la=[float("inf")]*pc
for i in range(1,pc+1):
    i10=str(Base_10_to_n(i, 2)).count("1")
    if i%i10==0:
      la[i-1]=1
    else:
      la[i-1]=la[(i%i10)-1]+1
if pc!=1:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append((x10-pow(2,n-i,pc-1))%(pc-1))
  for a in ans:
    if a==0:
      print(1)
    else:
      print(1+la[a-1])
else:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append("n")
  for a in ans:
    if a==0:
      print(1)
    elif a=="n":
      print(0)
    else:
      print(1+la[a-1])

### FIXED CODE ###

def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out#int outn=int(input())
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
n=int(input())
x=input()
ans=[]
pc=x.count("1")
la=[float("inf")]*pc
for i in range(1,pc+1):
    i10=str(Base_10_to_n(i, 2)).count("1")
    if i%i10==0:
      la[i-1]=1
    else:
      la[i-1]=la[(i%i10)-1]+1
if pc!=1:
  x10=Base_n_to_10(x,2)
  a=x10%(pc+1)
  b=x10%(pc-1)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((a+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append((b-pow(2,n-i,pc-1))%(pc-1))
  for a in ans:
    if a==0:
      print(1)
    else:
      print(1+la[a-1])
else:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append("n")
  for a in ans:
    if a==0:
      print(1)
    elif a=="n":
      print(0)
    else:
      print(1+la[a-1])
### BUGGY CODE ###

N = int(input())

a = 1
b = 1
ans = 0

while a<N:
    b = 1
    while a*b <N:
        ans += 1
        b += 1
    a+=1
print(ans)

### FIXED CODE ###

N = int(input())

a = 1
ans = 0

while a< N:
    b = a+1
    while a*b < N:
        ans += 2
        b += 1
    a+=1
a=1
while a**2 < N:
    ans+=1
    a += 1
print(ans)
### BUGGY CODE ###

N = int(input())
lists = [str(i) for i in range(1,N+1)]
count = 0
for i in range(0,N):
    for j in range(i,N):
        if lists[i][0] == lists[j][-1] and lists[i][-1] == lists[j][0]:
            if lists[i] == lists[j]:
                count = count + 1
            else:
                count = count + 2
print(count)

### FIXED CODE ###

N = int(input())
lists = [str(i) for i in range(1,N+1)]
count = 0
for i in range(1,10):
    for j in range(i,10):
        s_cnt, t_cnt = 0, 0
        si, sj = str(i), str(j)
        for k in lists:
            if k[0] == si and k[-1] == sj:
                s_cnt += 1
            elif k[0] == sj and k[-1] == si:
                t_cnt += 1
        if i != j:
            count += s_cnt * t_cnt * 2
        elif i == j:
            count += s_cnt ** 2
print(count)
### BUGGY CODE ###

# numpy使うときは、PyPyは不可
import numpy as np

N, K = map(int, input().split())
P = (np.array(list((map(int, input().split())))) + 1)

ans = 0

for num in range(len(P)):
    tmp = P[num:num+K].sum()
    if ans < tmp:
        ans = tmp

print(float(ans/2))



# 回答
# Pcum = np.zeros(N + 1, np.int32)
# Pcum[1:] = P.cumsum()
#
# length_K_sums = Pcum[K:] - Pcum[0:-K]
# print(length_K_sums.max() / 2)

### FIXED CODE ###

# numpy使うときは、PyPyは不可
import numpy as np

N, K = map(int, input().split())
P = (np.array(list((map(int, input().split())))) + 1)

"""
ans = 0

for num in range(len(p)):
    tmp = p[num:num+K].sum()
    if ans < tmp:
        ans = tmp

print(float(ans))

"""

# 回答
Pcum = np.zeros(N + 1, np.int32)
Pcum[1:] = P.cumsum()

length_K_sums = Pcum[K:] - Pcum[0:-K]
print(length_K_sums.max() / 2)
### BUGGY CODE ###

nmax, abmax, inf = 40, 10, 1000000

a, b, c = [0] * nmax, [0] * nmax, [0] * nmax
dp = [[[0] * (nmax * abmax + 1) for _ in range(nmax * abmax + 1)] for _ in range(nmax + 1)]

n, ma, mb = map(int, input().split())
for i in range(n):
  x, y, z = map(int, input().split())
  a[i], b[i], c[i] = x, y, z

for i in range(n + 1):
  for ca in range(nmax * abmax + 1):
    for cb in range(nmax * abmax + 1):
      dp[i][ca][cb] = inf

dp[0][0][0] = 0

for i in range(n):
  for ca in range(0, 401):
    for cb in range(0, 401):
      if dp[i][ca][cb] == inf:
        continue
      dp[i + 1][ca][cb] = min(dp[i + 1][ca][cb], dp[i][ca][cb])
      dp[i + 1][ca + a[i]][cb + b[i]] = min(dp[i + 1][ca + a[i]][cb + b[i]], dp[i][ca][cb] + c[i])

ans = inf
for ca in range(1, 401):
  for cb in range(1, 401):
    if ca * mb == cb * ma:
      ans = min(ans, dp[n][ca][cb])

if ans == inf:
  ans = -1

print(ans)


### FIXED CODE ###

import sys
inf = float('inf')
n, ma, mb = map(int, input().split())
t = [[inf] * 401 for _ in range(401)]
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(400, 0, -1):
    for bb in range(400, 0, -1):
      if t[aa][bb] == inf:
        continue
      if t[a + aa][b + bb] > c + t[aa][bb]:
        t[a + aa][b + bb] = c + t[aa][bb]
  if t[a][b] > c:
    t[a][b] = c
result = inf
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == inf:
  print(-1)
else:
  print(result)
### BUGGY CODE ###

from fractions import gcd
k = int(input())

ans = 0

lst = [[0 for _ in range(1, k+1)] for __ in range(k+1)]
cnt = [0 for _ in range(1, k+1)]


for i in range(1, k+1):
    for j in range(1, k+1):
        tmp = gcd(i,j)
        for l in range(1,k+1):
            ans += gcd(tmp,l)
            
print(ans)


### FIXED CODE ###

from fractions import gcd
k = int(input())

ans = 0

lst = [[0 for _ in range(1, k+1)] for __ in range(k+1)]
cnt = [0 for _ in range(1, k+1)]


for i in range(1, k+1):
    for j in range(1, k+1):
        lst[i-1][j-1] = [gcd(i, j)]
        cnt[gcd(i, j)-1] += 1

ans = 0

for i in range(k):
    for j in range(1, k+1):
        ans += cnt[i]*gcd((i+1),j)

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

from collections import Counter

H, W, M = map(int, input().split())

h = []
w = []
for _ in range(M):
    x, y = map(int, input().split())
    h.append(x)
    w.append(y)

ch = Counter(h)
cw = Counter(w)

h_max = max(ch.values())
w_max = max(cw.values())

h_idx = [x for (x, y) in ch.items() if y == h_max]
w_idx = [x for (x, y) in cw.items() if y == w_max]

boms = set([(x, y) for x, y in zip(h, w)])

minus = []
for x in h_idx:
    for y in w_idx:
        if (x, y) in boms:
            minus.append(-1)
        else:
            minus.append(0)

print(h_max + w_max + max(minus))

### FIXED CODE ###

H, W, M = map(int, input().split())

h = [0] * H
w = [0] * W
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x - 1] += 1
    w[y - 1] += 1
    boms.add((x, y))

h_max = max(h)
w_max = max(w)

h_idx = [x + 1 for x, y in enumerate(h) if y == h_max]
w_idx = [x + 1 for x, y in enumerate(w) if y == w_max]

minus = -1
for x in h_idx:
    for y in w_idx:
        if not (x, y) in boms:
            minus = 0
            break

print(h_max + w_max + minus)
### BUGGY CODE ###

import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=era(up)
like=[]

for i in range(len(s)):
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

for i in range(Q):
    print(sumli[r[i]]-sumli[l[i]-1])

### FIXED CODE ###

import math
import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data
    
def prime(n):
    max=int(math.sqrt(n))
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

Q=int(input())
l=[]
r=[]
up=0
for i in range(Q):
    a,b=map(int,input().split())
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=prime(up)
like=[]

for i in range(len(s)):#O(10000*log(10000))
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):#O(100000)
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

for i in range(Q):
    print(sumli[r[i]]-sumli[l[i]-1])