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

import numpy as np

S = list(input())
l = len(S) + 1
A = np.zeros(l, dtype=np.int16)
B = np.zeros(l, dtype=np.int16)

for i in range(len(S)):
    if S[i] == '<':
        A[i+1] = A[i] + 1

for i in range(len(S)-1, -1, -1):
    if S[i] == '>':
        B[i] = B[i+1] + 1
answer = (np.maximum(A, B)).sum()
print(answer)

### FIXED CODE ###

S = list(input())
A = [0] * (len(S)+1)
imos = [0] * (len(S))
for i in range(len(S)):
    if S[i] == '>':
        imos[i] = 1
    else:
        imos[i] = -10000000
imos += [0]
for i in range(len(S), 0, -1):
    imos[i-1] = max(0, imos[i-1] + imos[i])
A[0] = imos[0]
for i in range(len(S)):
    if S[i] == '<':
        A[i+1] = max(imos[i+1], A[i]+1)
    else:
        A[i+1] = max(0, min(A[i]-1, imos[i+1]))
print(sum(A))
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

R,G,B = reversed([R,G,B])
r = 0
count = 0
r_max = N // R

while r <= r_max:
    
    g_max = (N-r*R)//G
    g = 0
    while g <= g_max:
        b = (N-r*R-g*G)/B
        if b.is_integer() and b >= 0:
            count += 1

        g += 1
    
    r += 1

print(count)

### FIXED CODE ###

R,G,B,N = map(int,input().split())

count = 0
for r in range(0,N+1,R):
    for g in range(r,N+1,G):
        b = (N-g)/B
        if b.is_integer() and b >= 0:
            count += 1

print(count)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
A.insert(0, 0)
A.append(0)

B = []
for i in range(len(A)-1):
  B.append(A[i+1] - A[i])
B_abs = [abs(b) for b in B]

for j in range(1, N+1):
  M1 = sum(B_abs[:j-1])
  M2 = abs(B[j-1] + B[j])
  M3 = sum(B_abs[j+1:])
  M = M1 + M2 + M3
  print(M)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
A.insert(0, 0)
A.append(0)

B = []
for i in range(len(A)-1):
  B.append(A[i+1] - A[i])

B_abs = [abs(b) for b in B]
B_abs_cusum = [0]
cusum = 0
for j in B_abs:
  cusum += j
  B_abs_cusum.append(cusum)

for k in range(1, N+1):
  M1 = B_abs_cusum[k-1]
  M2 = abs(B[k-1] + B[k])
  M3 = B_abs_cusum[-1] - B_abs_cusum[k+1]
  M = M1 + M2 + M3
  print(M)
### BUGGY CODE ###

import itertools
import numpy as np

N = int(input())
L = np.sort(np.array(list(map(int, input().split(" ")))))[::-1]

xx = itertools.combinations(L, 3)
cnt = 0
for x in xx:
    if x[0] < x[1] + x[2]:
        cnt += 1
print(cnt)

### FIXED CODE ###

from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i):
        m = L[i]-L[j]
        k = bisect_right(L, m)
        n = max(0, j-k)
        ans+=n
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
seen=[False]*n

for _ in range(m):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=[-1]*n
q=deque([0])
while len(q):
    now=q.popleft()
    seen[now]=True
    for i in graph[now]:
        if seen[i]:
            continue
        q.append(i)
        if ans[i]==-1:
            ans[i]=now
print("Yes")
for i in range(1,n):
    print(ans[i]+1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)

def main():
    n,m=map(int,input().split())
    graph=[[] for _ in range(n)]
    seen=[False]*n

    for _ in range(m):
        a,b=map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=[-1]*n
    q=deque([0])
    seen[0]=True
    while len(q):
        now=q.popleft()
        for i in graph[now]:
            if seen[i]:
                continue
            seen[i]=True
            q.append(i)
            if ans[i]==-1:
                ans[i]=now
    print("Yes")
    for i in range(1,n):
        print(ans[i]+1)

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

from collections import Counter 
from collections import defaultdict
from collections import deque
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))

h,w=input_list()
a=[[s for s in  input()] for _ in range(h)]

l=[[0 for _ in range(w)] for _ in range(h)]
r=[[0 for _ in range(w)] for _ in range(h)]
u=[[0 for _ in range(w)] for _ in range(h)]
d=[[0 for _ in range(w)] for _ in range(h)]

a=np.array(a)
l=np.array(l)
r=np.array(r)
u=np.array(u)
d=np.array(d)
#left
for w_i in range(1,w):
    for h_i in range(h):

        if a[h_i][w_i]=="#" or a[h_i][w_i-1]=="#":
            continue
        l[h_i][w_i]=l[h_i][w_i-1]+1
    
#right
for w_i in range(w-2,-1,-1):
    for h_i in range(h):

        if a[h_i][w_i]=="#" or a[h_i][w_i+1]=="#":
            continue
        r[h_i][w_i]=r[h_i][w_i+1]+1


#up
for w_i in range(w):
    for h_i in range(1,h):

        if a[h_i][w_i]=="#" or a[h_i-1][w_i]=="#":
            continue
        u[h_i][w_i]=u[h_i-1][w_i]+1


#down
for w_i in range(w):
    for h_i in range(h-2,-1,-1):

        if a[h_i][w_i]=="#" or a[h_i+1][w_i]=="#":
            continue
        d[h_i][w_i]=d[h_i+1][w_i]+1
ans=0
for w_i in range(w):
    for h_i in range(h):
        if a[h_i][w_i]=="#":
            continue
        cal=l[h_i][w_i]+r[h_i][w_i]+u[h_i][w_i]+d[h_i][w_i]+1
        ans=max(ans,cal)

print(ans)



### FIXED CODE ###

#import numpy as np
h,w=list(map(int,input().split()))
s=[[i for i in input() ] for _ in range(h)]

l=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
r=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
u=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
d=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
for h_i in range(h):
    for w_i in range(w):
        rev_w=w-w_i-1
        rev_h=h-h_i-1
        if s[h_i][w_i]!="#" and w_i!=0:
            l[h_i][w_i]+=l[h_i][w_i-1]
        if s[h_i][rev_w]!="#" and w_i!=0:
            r[h_i][rev_w]+=r[h_i][rev_w+1]
        if s[h_i][w_i]!="#" and h_i!=0:
            u[h_i][w_i]+=u[h_i-1][w_i]
        if s[rev_h][w_i]!="#" and h_i!=0:
            d[rev_h][w_i]+=d[rev_h+1][w_i]
ans=0
for h_i in range(h):
    for w_i in range(w):
        tmp=l[h_i][w_i]+r[h_i][w_i]+u[h_i][w_i]+d[h_i][w_i]-3
        ans=max(ans,tmp)

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

N,M=map(int,input().split())
def bikkuri(A):
    ans=1
    for i in range(A):
        ans*=i+1
    ans%=1000000007
    return ans

if N==M:
    p=2*bikkuri(N)*bikkuri(M)
    p%=1000000007
elif  abs(N-M)==1:
    p=bikkuri(M)*bikkuri(N)
    p%=1000000007
else:
    p=0
print(p)


### FIXED CODE ###

N,M=map(int,input().split())
def bikkuri(A):
    ans=1
    for i in range(A):
        ans*=i+1
        ans%=1000000007
    return ans

if N==M:
    p=2*(bikkuri(N)*bikkuri(M)%1000000007)
    p%=1000000007
elif  abs(N-M)==1:
    p=(bikkuri(M)*bikkuri(N)%1000000007)
    p%=1000000007
else:
    p=0
print(p)
### BUGGY CODE ###

N = int(input())
line = list(map(int, input().split()))
n = N - 1
ans = 1
while(len(line) >= 0):
    c = line.count(n)
    if (len(line) == 0):
        print(ans % (10**9+7))
        break
    if len(line) == 1 and line[0] == 0:
        print(ans % (10**9+7))
        break
    elif c != 2:
        print(0)
        break
    else:
        ans *= 2
        line = [i for i in line if i != n]
        n = n - 2


### FIXED CODE ###

N = int(input())
line = list(map(int, input().split()))
n = N - 1
ans = 1
line.sort()
s = len(line)
index = s - 1
while(index > 1):
    if line[index] == n and line[index-1] == n:
        ans *= 2
        n = n - 2
        index = index - 2
    else:
        print(0)
        break

if index == 1:
    if line[index] == n and line[index-1] == n:
        ans *= 2
        print(ans % (10**9+7))
    else:
        print(0)

elif index == 0:
    if line[0] == 0:
        print(ans % (10**9+7))
    else:
        print(0)
### BUGGY CODE ###

N = int(input())
i = 2
while True:
    if i / N == 0:
        print(i)
        break
    i += 2

### FIXED CODE ###

N = int(input())
i = 2
if N % 2 == 0:
    print(N)
else:
    print(N * 2)
### BUGGY CODE ###



# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n,m = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

a.sort(reverse=True)

from heapq import *

ans = 0
q = []
heappush(q,(-2*a[0],0,0))


num = 0
while num < m:
    v,i,j = heappop(q)
    v = -v
    ans += v
    num += 1
    if i != j:
        if num < m:
            num += 1
            ans += v
        else:
            break
        
    #print(v,i,j,num)
    if j == 0 and i < n-1:
        heappush(q,(-(a[i+1]+a[j]),i+1,j))
    if i > j:
        heappush(q,(-(a[i]+a[j+1]),i,j+1))

print(ans)






"""
n,k = [int(i) for i in readline().split()]
r,s,p = [int(i) for i in readline().split()]
t = input()

ans = 0

for i in range(k):
    tt = t[i::k]
    l = len(tt)
    dpr = dps = dpp = 0
    for i in tt:
        if i == "r":
            dpr,dps,dpp = max(dps,dpp),max(dpr,dpp),max(dps,dpr)+p
        if i == "s":
            dpr,dps,dpp = max(dps,dpp)+r,max(dpr,dpp),max(dps,dpr)
        if i == "p":
            dpr,dps,dpp = max(dps,dpp),max(dpr,dpp)+s,max(dps,dpr)

    ans += max(dpr,dps,dpp)


print(ans)
"""

### FIXED CODE ###


# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n,m = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

#a.sort(reverse=True)

a.sort()



def check(mid):
    num = 0
    p = 0
    for i in range(n-1,-1,-1):
        c = 0
        while p<n and a[p]+a[i] < mid:
            p += 1
        num += n-p
    #print(mid,num,"mn")
    return num


ok = a[0]*2-1
ng = a[-1]*2+1

while ng - ok > 1:
    mid = (ng+ok)//2
    c = check(mid)
    if c<m:
        ng = mid
    else:
        ok = mid
    
    #print(ok,ng)
    
#print(ok)
    



ans = 0
p = n-1
num = 0

res = [0]*n
for i in range(n):
    c = 0
    while p>=0 and a[p]+a[i] >= ng:
        p -= 1
    res[i] = n-1-p
    num += n-1-p

for i in range(n):
    ans += res[i]*a[i]
ans *= 2
#print(ans,num)
print(ans+ok*(m-num))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j >= 0:
            dp[i] = min(abs(h[i-j] - h[i]) + dp[i-j], dp[i])
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j >= 0:
            dp[i] = min(abs(h[i-j] - h[i]) + dp[i-j], dp[i])
print(dp[-1])
### BUGGY CODE ###

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

res = []
for i in range(2, min(A, B)+1):
    if A % i == 0:
        if B % i == 0:
            res.append(i)

i = 0
while i < len(res)-1:
    j = i + 1
    while j < len(res):
        if res[j] % res[i] == 0:
            res.pop(j)
        else:
            j += 1
        
    i += 1

print(len(res)+1)

### FIXED CODE ###

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

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

x = gcd(A, B)

res = 1
temp = x
for i in range(2, int(-(-x**0.5//1))+1):
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        res += 1

if temp!=1:
    res += 1

print(res)
### BUGGY CODE ###

t=str(input())
j=1
a= str()
for i in t:
    if i=="?":
        i="D"
    a=a+i
print(a)



### FIXED CODE ###

t=str(input())
print(t.replace("?","D"))
### BUGGY CODE ###

n = int(input())
p_n = list(map(int, input().split()))
ans = 1
p_i_1 = [p_n[0]]
for i in range(1, n):
    if min(p_i_1) > p_n[i]:
        ans += 1
    p_i_1.append(p_n[i])
print(ans)


### FIXED CODE ###

n = int(input())
p_n = list(map(int, input().split()))
ans = 1
p_i_1 = [p_n[0]]
m = p_n[0]
for i in range(1, n):
    if m > p_n[i]:
        ans += 1
    m = min(m, p_n[i])
    p_i_1.append(p_n[i])
    if m == 1:
        break
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    print("-1")
else:
    print(ans)

### FIXED CODE ###


n = int(input())
a = list(map(int, input().split()))
ans = 1
a.sort()
if a[0] == 0:
    print(0)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > pow(10, 18):
        print(-1)
        exit()
else:
    print(ans)
### BUGGY CODE ###

z = list(map(int, input().split()))
a,b,c,d,cnt = z[0],z[1],z[2],z[3],0
while(a <= b):
    if (a%c != 0 and a%d != 0):
        cnt += 1
    a += 1
print(cnt)

### FIXED CODE ###

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

def lcm(a,b):
    return a*b // gcd(a,b)

a,b,c,d = map(int,input().split())
a -= 1
A = a-((a//c) + (a//d) - a//lcm(c,d))
B = b-((b//c) + (b//d) - b//lcm(c,d))
print(B-A)
### BUGGY CODE ###

n,m=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
card=[0]*n

for i in range(m):
    l,r=lr[i]
    for j in range(l-1,r):
        card[j]+=1
ans=0
for k in range(n):
    if card[k] == m:
        ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
l=1
r=n
for i in range(m):
    ll,rr = map(int,input().split())
    l=max(l,ll)
    r=min(r,rr)
if l<=r:
    print(r-l+1)
else:
    print(0)
### BUGGY CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False

for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = 2
            else:
                i[1] = 1
        if int(i[1]) == 1:
            lead+=i[2]
        else:
            end+=i[2]

lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)
### BUGGY CODE ###

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

while 1:
        if A + 1 != B:
                A += 1
        elif A - 1 != 0:
                A -= 1
        else:
                print("Borys")
                break
    
        if B - 1 != A:
                B -= 1
        elif B + 1 != N:
                B += 1
        else:
                print("Alice")
                break

### FIXED CODE ###

N, A, B = map(int, input().split())
if (A % 2 == 0) ^ (B % 2 == 0): 
        print("Borys")
else:
        print("Alice")
### BUGGY CODE ###

N = int(input())
L = [input() for i in range(N)]
l = list(set(L))
l.sort()
c = [L.count(j) for j in l]
C = max(c)
[print(k) for k in l if L.count(k) == C]

### FIXED CODE ###

import collections
N = int(input())
l = [input() for i in range(N)]
L = collections.Counter(l)
a = L.most_common()
M = a[0][1]
A = [j[0] for j in a if j[1] == M]
[print(k) for k in sorted(A)]
### BUGGY CODE ###

a, b = map(int, input().split())
for k in range(10**9):
  if (a+k) == (b+k):
    print(k)
    exit()
print("IMPOSSIBLE")

### FIXED CODE ###

a, b = map(int, input().split())
if (a+b)%2 != 0:
  print("IMPOSSIBLE")
else:
  print((a+b)//2)
### BUGGY CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
dp=[[0 for j in range(w+1)] for i in range(n+1)]
for i in range(n):
  for j in range(w+1):
    if l[i][0]<=j:
      dp[i+1][j]=max(dp[i][j],dp[i][j-l[i][0]]+l[i][1])
    else:
      dp[i+1][j]=dp[i][j]
print(dp[n][w])


### FIXED CODE ###

import numpy as np
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv=np.array(wv)
dp=[0]*(W+1)
dp=np.array(dp)
for w,v in wv:
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[W])
### BUGGY CODE ###

h, w = map(int, input().split())
grid = [0]*h
for i in range(h):
  grid[i] = input()

counter = [[[0, 0] for j in range(w)] for i in range(h)]
ans = 0
for i in range(h):
  for j in range(w):
    if grid[i][j] == "#":
      continue
    if i == 0 or (i != 0 and grid[i-1][j] == "#"):
      k = 0
      while i+k < h and grid[i+k][j] == ".":
        k += 1
      counter[i][j][0] = k-1
    else:
      counter[i][j][0] = counter[i-1][j][0]
    if j == 0 or (j != 0 and grid[i][j-1] == "#"):
      k = 0
      while j+k < w and grid[i][j+k] == ".":
        k += 1
      counter[i][j][1] = k-1
    else:
      counter[i][j][1] = counter[i][j-1][1]
    if ans < counter[i][j][0]+counter[i][j][1]:
      ans = counter[i][j][0]+counter[i][j][1]
print(ans+1)

### FIXED CODE ###

h, w = map(int, input().split())
grid = [0]*h
for i in range(h):
  grid[i] = input()

counter = [[[0, 0] for j in range(w)] for i in range(h)]
ans = 0
for i in range(h):
  for j in range(w):
    if grid[i][j] == "#":
      continue
    if i == 0 or (i != 0 and grid[i-1][j] == "#"):
      k = 0
      while i+k < h and grid[i+k][j] == ".":
        k += 1
      counter[i][j][0] = k-1
    else:
      counter[i][j][0] = counter[i-1][j][0]
    if j == 0 or (j != 0 and grid[i][j-1] == "#"):
      k = 0
      while j+k < w and grid[i][j+k] == ".":
        k += 1
      counter[i][j][1] = k-1
    else:
      counter[i][j][1] = counter[i][j-1][1]
    if ans < counter[i][j][0]+counter[i][j][1]:
      ans = counter[i][j][0]+counter[i][j][1]
print(ans+1)
### BUGGY CODE ###

n = int(input())
S = input()
cnt = 0
set_ = set()
for val in range(1000):
    val = str(val).zfill(3)
    a =val[0]
    b = val[1]
    c = val[2]
    for i in range(n):
        if S[i]==a:
            for j in range(i+1,n):
                if S[j]==b:
                    for k in range(j+1,n):
                        if S[k]==c and S[i]+S[j]+S[k] not in set_: 
                            cnt += 1
                            set_.add(S[i]+S[j]+S[k])
print(cnt)

### FIXED CODE ###

n = int(input())
S = input()
cnt = 0
set_ = set()
for val in range(1000):
    val = str(val).zfill(3)
    a =val[0]
    b = val[1]
    c = val[2]
    flag = False
    for i in range(n):
        if S[i]==a and flag == False:
            for j in range(i+1,n):
                if S[j]==b and flag == False:
                    for k in range(j+1,n):
                        if S[k]==c and flag == False: 
                            cnt += 1
                            flag = True
                            break
                    break
            break
print(cnt)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [k for k in range(1,10**5+1)]
s = set(a)
for i in range(m):
  l,r = map(int,input().split())
  ml = [p for p in range(l,r+1)]
  newset = set(ml)
  s = s&newset
print(len(s))

### FIXED CODE ###

n,m = map(int,input().split())
L = []
R = []
for i in range(m):
  l,r = map(int,input().split())
  L.append(l)
  R.append(r)

ans = min(R)-max(L)+1
print(ans if ans >0 else "0")
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=tuple(map(int,input().split()))
b=tuple(map(int,input().split()))
c=tuple(map(int,input().split()))

def f(p,q):
    return [i+j for j in q for i in p]

if x+y<y+z:
    for i in sorted(f(c,f(a,b)))[::-1][:k]:
        print(i)
elif x+z<y+z:
    for i in sorted(f(b,f(a,c)))[::-1][:k]:
        print(i)
else:
    for i in sorted(f(a,f(b,c)))[::-1][:k]:
        print(i)

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
 
AB = sorted([a + b for a in A for b in B])[-1:-K-1:-1]
ABC = sorted([ab + c for ab in AB for c in C])[-1:-K-1:-1]
print('\n'.join(map(str, ABC)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if is_prime3(i) == True and (i+1) % 2 == 0:
			tmp = (i+1) / 2
			tmp = int(tmp)
			if is_prime3(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print(base[r] - base[l-1])
			
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

n,m = map(int, input().split())
from_start = []
to_end = []

for _ in range(m):
  temp = []
  temp = list(map(int, input().split()))
  if temp[0]==1:
    from_start.append(temp[1])
  elif temp[1]==n:
    to_end.append(temp[0])
else:
  for i in from_start:
    if i in to_end:
      print('POSSIBLE')
      break
  else:
    print('IMPOSSIBLE')
    

### FIXED CODE ###

n,m = map(int, input().split())
set_a = set()
set_b = set()
AB = [list(int(x) for x in input().split()) for _ in range(m)]


for a,b in AB:
  if a > b:
    a,b = b,a
  
  if a == 1:
    set_a.add(b)
  if b == n:
    set_b.add(a)

se = set_a & set_b
print('POSSIBLE' if se else 'IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_sub_list = [a - (i + 1) for i, a in enumerate(A_list)]
b_max = max(A_sub_list)
b_min = min(A_sub_list)
min_s = pow(10, 10)
for b in range(b_min, b_max + 1):
    s = sum([abs(a - b) for a in A_sub_list])
    min_s = min(min_s, s)
print(min_s)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
B_list = [a - (i + 1) for i, a in enumerate(A_list)]
B_list.sort()
b = B_list[int(len(B_list) / 2)]
s = sum([abs(B - b) for B in B_list])
print(s)
### BUGGY CODE ###

import math
from functools import reduce
import itertools



def gcd(*numbers):
    return reduce(math.gcd, numbers)


a = int(input())
ans = 0
nums = []
for i in range(1, a+1):
    nums.append(i)

for balls in itertools.product(nums, repeat=3):
    ans += int(gcd(gcd(balls[0], balls[1]), balls[2]))

print(ans)


### FIXED CODE ###

from math import gcd

a = int(input())

ans = 0
for i in range(1, a+1):
    for k in range(1, a+1):
        for j in range(1, a+1):
            ans += gcd(gcd(i,k),j)


print(ans)