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

import math
A, B = map(int,input().split())
A_cf = []
B_cf = []
for i in range(1,int(A**0.5)+1):
    if A % i == 0:
        A_cf.append(i)
        if i != A // i:
            A_cf.append(A//i)
for i in range(1,int(B**0.5)+1):
    if B % i == 0:
        B_cf.append(i)
        if i != B // i:
            B_cf.append(B//i)
DA = dict()
for i in range(len(A_cf)):
    DA[A_cf[i]] = False

for i in range(len(B_cf)):
    if B_cf[i] in DA:
        DA[B_cf[i]] = True
cf = []
for i in range(len(A_cf)):
    if DA[A_cf[i]]:
        if A_cf[i] % 2 == 0 and A_cf[i] != 2:
            continue
        cf.append(A_cf[i])
prime_num = []
cf.sort()
"""
def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    m = math.floor(math.sqrt(n)) + 1
    for p in prime_num:
        if n % p == 0:
            return False
        if p > m:
            break
    return True
"""
def isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = math.floor(n/2) + 1
    for p in range(3,m,2):
        if n % p == 0:
            return False
    return True

for i in range(len(cf)):
    if isPrime(cf[i]):
        prime_num.append(cf[i])

ans = len(prime_num) + 1
print(ans)

### FIXED CODE ###

import math
A, B = map(int,input().split())
A_cf = []
B_cf = []
for i in range(1,int(A**0.5)+1):
    if A % i == 0:
        A_cf.append(i)
        if i != A // i:
            A_cf.append(A//i)
for i in range(1,int(B**0.5)+1):
    if B % i == 0:
        B_cf.append(i)
        if i != B // i:
            B_cf.append(B//i)
DA = dict()
for i in range(len(A_cf)):
    DA[A_cf[i]] = False

for i in range(len(B_cf)):
    if B_cf[i] in DA:
        DA[B_cf[i]] = True
cf = []
for i in range(len(A_cf)):
    if DA[A_cf[i]]:
        if A_cf[i] % 2 == 0 and A_cf[i] != 2:
            continue
        cf.append(A_cf[i])
prime_num = []
cf.sort()

def isPrime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
for i in range(len(cf)):
    if isPrime(cf[i]):
        prime_num.append(cf[i])

ans = len(prime_num) + 1
print(ans)
### BUGGY CODE ###

n=int(input())
numbers=input().split()
nm=list(map(int,numbers))
#print(nm)
sums=0
for i in range(0,n-1):
    for j in range(i+1,n):
        #print(nm[i],end=" ")
        #print(nm[j])
        sums+=nm[i]^nm[j]
#print(sums)
print(sums%1000000007)

### FIXED CODE ###

n=int(input())
numbers=input().split()
nums=list(map(int,numbers))
#print(nums)
mx=0
for num in nums:
    if num>mx:
        mx=num
#print(mx)
j=0
ans=0
while 2**j<=mx:
    sm=0
    for num in nums:
        sm+= num>>j &1
    ans+=(sm)*(n-sm)*2**j
    j=j+1
#print(ans)
print(ans%1000000007)
### BUGGY CODE ###

n, m = map(int, input().split())
broken_list = [int(input()) for _ in range(m)]
a = [0] * (n+1)
a[0] = 1
a[1] = 0 if 1 in broken_list else 1
 
if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in range(2, n+1):
  if i in broken_list:
    a[i] = 0
  else:
    a[i] = a[i-1] + a[i-2]
 
print(a[n]%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())

a = 1
b = 1

i = 2

for j in range(m):
  ind = int(input())
  if ind == 1:
    b = 0
    continue
  while i < ind:
    a, b = b, a+b
    i += 1
  else:
    a, b = b, 0
    i += 1
    
while i < n+1:
  a, b = b, a+b
  i += 1
  
  
print(b%1000000007)
### BUGGY CODE ###

N = int(input())

S = []

for i in range(N):
  S.append(str(input()))

cnt_ar = list(set(S))
cnt_ar.sort()

ar = []

for i in range(len(cnt_ar)):
  ar.append(S.count(cnt_ar[i]))

for i in range(len(ar)):
  if ar[i] == max(ar):
    print(cnt_ar[i])


### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)
### BUGGY CODE ###

N, Q = map(int, input().split())
rcx = [tuple(map(int, input().split())) for _ in range(Q)]

thres_1, thres_2 = N, N
nearest_white_1 = [N] * N
nearest_white_2 = [N] * N

reverse_count = 0
for rc, x in rcx:
    if rc == 1:
        if x < thres_1:
            reverse_count += thres_2 - 2
            for i in range(1, thres_2):
                nearest_white_2[i] = x
            thres_1 = x
        else:
            reverse_count += nearest_white_1[x] - 2
    else:
        if x < thres_2:
            reverse_count += thres_1 - 2
            for i in range(1, thres_1):
                nearest_white_1[i] = x
            thres_2 = x
        else:
            reverse_count += nearest_white_2[x] - 2

    #print(reverse_count)
    #print(f"thres1:{thres_1} {nearest_white_1}")
    #print(f"thres2:{thres_2} {nearest_white_2}")
    #print('-'*20)

print((N-2)**2 - reverse_count)

### FIXED CODE ###

N, Q = map(int, input().split())
rcx = [tuple(map(int, input().split())) for _ in range(Q)]

thres_1, thres_2 = N-2, N-2
nearest_white_1 = [0] * (N-2)
nearest_white_2 = [0] * (N-2)

reverse_count = 0
for rc, x in rcx:
    x = x-2
    if rc == 1:
        if x < thres_1:
            for i in range(x+1, thres_1):
                nearest_white_1[i] = thres_2
            thres_1 = x
            reverse_count += thres_2
        else:
            reverse_count += nearest_white_1[x]
    else:
        if x < thres_2:
            for i in range(x+1, thres_2):
                nearest_white_2[i] = thres_1
            reverse_count += thres_1
            thres_2 = x
        else:
            reverse_count += nearest_white_2[x]

    #print(reverse_count)
    #print(f"thres1:{thres_1} {nearest_white_1}")
    #print(f"thres2:{thres_2} {nearest_white_2}")
    #print('-'*20)

print((N-2)**2 - reverse_count)
### BUGGY CODE ###

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	x = 0
	for L in range(N):
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N
		indt = L-1
		while L2ind==-1 and indt>=0:
			if P[indt]>=P[L]:
				if L1ind==-1:
					L1ind = indt
				elif L2ind==-1:
					L2ind = indt
			indt -= 1

		indt = L+1
		while R2ind==N and indt<=N-1:
			if P[indt]>=P[L]:
				if R1ind==N:
					R1ind = indt
				elif R2ind==N:
					R2ind = indt		
			indt += 1

		x += ((L1ind-L2ind)*(R1ind-L) + (L-L1ind)*(R2ind-R1ind))*P[L]

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

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

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1+m)]
tree_go = [[] for i in range(n+1)]
tree_come = [[] for i in range(n+1)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
excess = []
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  for y in tree_go[x]:
    que.append((y,x))
print(*parent[1:],sep="\n")


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1+m)]
tree_go = [[] for i in range(n+1)]
tree_come = [[] for i in range(n+1)]
excess = [0 for i in range(n+1)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
  if len(tree_come[i]) >= 2:
    excess[i] = len(tree_come[i])-1
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
visited = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  if excess[x] >= 1:
    excess[x] -= 1
    continue
  for y in tree_go[x]:
    que.append((y,x))
print(*parent[1:],sep="\n")
### BUGGY CODE ###

A,B,C,D=map(int, input().split())
def lcm(a, b):
    if a>b:
        grater = a
    else:
        grater = b
    while(True):
        if((grater%a == 0) and (grater%b == 0)):
            lcm = grater
            break
        else:
            grater += 1
    return lcm

def f(X, a, b):
    return (X - X//a - X//b + X//lcm(a, b))

sum = f(B, C, D) - f(A-1, C, D)
print(sum)

### FIXED CODE ###

A,B,C,D=map(int, input().split())
def gcd(a, b):
    remainder = max(a, b) % min(a, b)
    if remainder == 0:
        return min(a, b)
    return gcd(min(a, b), remainder)

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

def f(X, a, b):
    return (X - X//a - X//b + X//lcm(a, b))

sum = f(B, C, D) - f(A-1, C, D)
print(sum)
### BUGGY CODE ###

N=int(input())
*A,=map(int,input().split())
t=10**9+7
S=[a%t for a in A]

ans=0
for i in range(N):
    for j in range(i+1,N):
       ans+=S[i]*S[j]
print(ans%t)

### FIXED CODE ###

N=int(input())
*A,=map(int,input().split())
t=10**9+7
S=[a%t for a in A]
g=sum(S)

ans=0
for i in range(N):
       g-=S[i]
       ans+=S[i]*g%t
print(ans%t)
### BUGGY CODE ###

#coding:utf-8
import copy
x, y, a, b, c = map(int, input().split())
p = input().split()
q = input().split()
r = input().split()
lis = [p,q,r]
coco = 0
for i in [len(p),len(q),len(r)]:
  for j in range(i):
    lis[coco][j] = int(lis[coco][j])
  coco += 1

def pick(list1,list2,number):
    list_f = copy.copy(list1)
    list_f2 = copy.copy(list1)
    list_s = copy.copy(list2)
    list_f2.extend(list_s)
    list_f2.sort(reverse = True)
    total_deli = 0
    for i in range(number):
        delic = list_f2[0]
        total_deli += int(delic)
        if(delic not in list_f):
            list_s.remove(delic)
        list_f2.remove(delic)
    return total_deli, list_s


ans1 = 0
ans2 = 0
ans3 = 0
clear_apple = []

#パターン1：赤リンゴから緑のリンゴへ
ans1,clear_apple = pick(p,r,x)
ans2,clear_apple = pick(q,clear_apple,y)
ans3 = ans1 + ans2

#パターン2：緑のリンゴから赤のリンゴへ
ans1,clear_apple = pick(q,r,y)
ans2,clear_apple = pick(p,clear_apple,x)
ans2 = ans1 + ans2

ans = max(ans2,ans3)
print("{}".format(ans))

### FIXED CODE ###

#coding:utf-8
x, y, a, b, c = map(int, input().split())
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p.sort(reverse = True)
q.sort(reverse = True)

p = p[0:x]
q = q[0:y]

p.extend(q)
p.extend(r)
p.sort(reverse = True)

ans = 0

for i in range(x + y):
  ans += p[i]
  
print("{}".format(ans))
### BUGGY CODE ###

import itertools

n=int(input())
li=[]
ans=0

for i in range(n):
    s=input()
    if s[0]=="M" or s[0]=="A" or s[0]=="R" or s[0]=="C" or s[0]=="H":
        li.append(s)

tm=(list(itertools.combinations(li,3)))

for j in tm:
    if j[0][0]!=j[1][0] and j[1][0]!=j[2][0] and j[2][0]!=j[0][0]:
        ans+=1

print(ans)
        

### FIXED CODE ###

import itertools

n=int(input())
li=[]

for i in range(n):
    li.append(input()[0])

tm=list(itertools.combinations(["M","A","R","C","H"],3))
ans=0

for j1,j2,j3 in tm:
    ans+=li.count(j1)*li.count(j2)*li.count(j3)

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 and 0 not in a:
    print(-1)
    break
else:
  print(ans)

### FIXED CODE ###

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

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass

n = ni()
p = divisor(n)
s = set()
for k in p:
    nk = n // k
    for t in divisor(nk - 1):
        s.add(t*k)
ans = 0
s.remove(1)
s.add(n)
for t in s:
    m = n
    while m % t == 0:
        m //= t
    if m % t == 1:
        ans += 1
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass

n = ni()
p = divisor(n)
s = set()
for k in p:
    nk = n // k
    for t in divisor(nk - 1):
        s.add(t*k)
ans = 0
s.remove(1)
s.add(n)
for t in s:
    m = n
    while m % t == 0:
        m //= t
    if m % t == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), dtype=np.int64)

for j in range(k):
    b = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        b[max(i-a[i], 0)] += 1
        b[min(i+a[i]+1, n)] -= 1
    a = np.cumsum(b)[:-1]
    if np.all(a==n):
        print(*a)
        break
else:
    print(*a)

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

readline = sys.stdin.readline

@njit('i8,i8,i8[::1]',cache=True)
def loop(n,k,a):
    for j in range(k):
        b = np.zeros(n+1, dtype=np.int64)
        for i in range(n):
            b[max(i-a[i], 0)] += 1
            b[min(i+a[i]+1, n)] -= 1
        a = np.cumsum(b)[:-1]
        if np.all(a==n):
            return(a)
            break
    else:
        return(a)


n, k = map(int, readline().split())
a = np.array(readline().split(), dtype=np.int64)

ans = loop(n,k,a)
print(*ans)
### BUGGY CODE ###

n,k = map(int,input().split())

A = list(map(int,input().split()))
sum = 0
import collections

c = collections.Counter(A)
c = c.most_common()
while len(c) > k:
    sum += c[-1][1]
    c = c[:-1]
print(sum)

### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline
n,k = map(int,input().split())

A = list(map(int,input().split()))
sum = 0
c = collections.Counter(A)
c = c.most_common()
if len(c) > k:
  a = len(c)-k
  c = c[-a:]
  for i in range(a):
    sum += c[i][1]
  print(sum)
else:
  print(0)
### BUGGY CODE ###

from sys import stdin

def main():
    n, m = list(map(int, stdin.readline().split()))
    hList = list(map(int, stdin.readline().split()))
    ABList = [list(map(int, stdin.readline().split())) for _ in range(m)]
    hRelations = [[0 for _ in range(n)] for _ in range(n)]
    for a, b in ABList:
        if hList[a-1] >= hList[b-1]:
            hRelations[b-1][a-1] = 1
        if hList[b-1] >= hList[a-1]:
            hRelations[a-1][b-1] = 1
    total = 0
    for hRelation in hRelations:
        if hRelation.count(1) == 0:
            total += 1
    print(total)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
import numpy as np


def main():
    n, m = list(map(int, stdin.readline().split()))
    hList = list(map(int, stdin.readline().split()))
    ABList = [list(map(int, stdin.readline().split())) for _ in range(m)]
    maxHeights = np.zeros(n)
    for a, b in ABList:
        if hList[a-1] >= maxHeights[b-1]:
            maxHeights[b-1] = hList[a-1]
        if hList[b-1] >= maxHeights[a-1]:
            maxHeights[a-1] = hList[b-1]
    total = 0
    i = 0
    for maxHeight in maxHeights:
        if maxHeight < hList[i]:
            total += 1
        i += 1
    print(total)


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

N = int(input())
A = []
while N>0:
    if N==1:
        A.append(1)
        break
    high = N
    low = 0
    while True:
        mid = (high+low)//2
        if N<=((mid-1)*mid)//2:
            high = mid
        elif N>(mid*(mid+1))//2:
            low = mid
        else:
            break
    A.append(mid)
    N -= mid
for i in range(len(A)):
    print(A[i])
    

### FIXED CODE ###

N = int(input())
A = []
while N>0:
    if N==1:
        A.append(1)
        break
    if N==2:
        A.append(2)
        break
    high = N
    low = 0
    while True:
        mid = (high+low)//2
        if N<=((mid-1)*mid)//2:
            high = mid
        elif N>(mid*(mid+1))//2:
            low = mid
        else:
            break
    A.append(mid)
    N -= mid
for i in range(len(A)):
    print(A[i])
### BUGGY CODE ###

def main():
    N = int(input())
    X = int(input(), 2)

    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c
    for i in range(N):
        print(f(X ^ (1 << (N - 1 - i))))


main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    X = int(S, 2)
    C = S.count('1')
    xc0 = X % (C + 1)
    xc1 = X % (C - 1) if C > 1 else 0

    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c

    for i, s in enumerate(S):
        k = N - 1 - i
        if s == '0':
            print(f((xc0 + pow(2, k, C + 1)) % (C + 1)) + 1)
        else:
            if C > 1:
                print(f((xc1 - pow(2, k, C - 1)) % (C - 1)) + 1)
            else:
                print(0)


main()
### BUGGY CODE ###

h,w,m=map(int,input().split())

max_h=[0 for i in range(h+1)]
max_w=[0 for i in range(w+1)]
grid=[[0 for i in range(w)] for j in range(h)]
pro=[list(map(int,input().split())) for i in range(m)]
pro.sort()
for i in range(m):
    h=pro[i][0]
    w=pro[i][1]
    max_h[h]+=1
    max_w[w]+=1
    grid[h-1][w-1]=1
h_max=[i for i, x in enumerate(max_h) if x == max(max_h)]
w_max=[i for i, x in enumerate(max_w) if x == max(max_w)]

ans=0
for i in h_max:
    for j in w_max:
        cnt=0
        cnt +=list(zip(*grid))[j-1].count(1)
        cnt += grid[i-1].count(1)
        if grid[i-1][j-1]==1:
            cnt -= 1
        
        if cnt > ans:
            ans=cnt
print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
row=[0]*H #x座標を入れるっちゅうかカウント
col=[0]*W #y座標を入れる
 
mat=[] #座標を入れる
 
for i in range(M):
    h, w = map(int, input().split())
    row[h-1]+=1
    col[w-1]+=1
    mat.append((h-1,w-1))
r=max(row)
c=max(col)
 
rr=[1 if row[i]==r else 0 for i in range(H)] #maxな列のインデックス
cc=[1 if col[i]==c else 0 for i in range(W)] #maxな行のインデックス
 
x=0 #maxな列と行の交差点にある爆弾の個数をカウント
for k in mat:
    if rr[k[0]]==1 and cc[k[1]]==1:
        x+=1
        
if sum(rr)*sum(cc)==x: #行と列の全ての交差点に爆弾があれば-1する
    print(r+c-1)
else:
    print(r+c)
### BUGGY CODE ###

a, b  = [int(i) for i in input().split()]
 
def divisor(n):
  i = 1
  table = []
  while i * i <= n:
    if n%i == 0:
      table.append(i)
      table.append(n//i)
    i += 1
  table = list(set(table))
  return table
 
def sieve(n):
  is_prime = [True for _ in range(n+1)]
  is_prime[0] = False
  for i in range(2, n+1):
    if is_prime[i-1]:
      j = 2 * i
      while j <= n:
        is_prime[j-1] = False
        j += i
  table = [ i for i in range(1, n+1) if is_prime[i-1]]
  return is_prime, table
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
m = gcd(a,b)
_, sosu = sieve(m)
print(1+len(set(sosu)&set(divisor(m))))

### FIXED CODE ###

# a, bを素因数分解する。O(ルートa + ルートb)
# 共通の素因数を見つける。O(loga + logb)

a,b = map(int, input().split())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a_prime = set(prime_factorize(a))
b_prime = set(prime_factorize(b))
ans = 0
for ap in a_prime:
  for bp in b_prime:
    if ap == bp:
      ans += 1
      break
print(ans+1)
### BUGGY CODE ###

K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)

cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp




### FIXED CODE ###

K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)
    exit()


cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp
### BUGGY CODE ###

import heapq

n=int(input())
G=[]
for index in range(n):
    x,y=map(int,input().split())
    G.append((index,x,y))

#print(G)

D=[[] for _ in range(n)]

xG=sorted(G,key=lambda x:x[1])
for index_x in range(n-1):
    nowx=xG[index_x]
    nextx=xG[index_x+1]
    distx=nextx[1]-nowx[1]
    D[nowx[0]].append([distx,nextx[0]])
    D[nextx[0]].append([distx,nowx[0]])

#print(xG)

yG=sorted(G,key=lambda x:x[2])
for index_y in range(n-1):
    nowy=yG[index_y]
    nexty=yG[index_y+1]
    disty=nexty[2]-nowy[2]
    D[nowy[0]].append([disty,nexty[0]])
    D[nexty[0]].append([disty,nowy[0]])

#print(yG)

#print(D)

def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in D[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in D[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

ans=prim_heap()
print(ans)






### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N=int(input())
G=[]
for i in range(N):
    x,y=map(int,input().split())
    G.append((x,y,i))

Gx=sorted(G,key=lambda x:x[0])
Gy=sorted(G,key=lambda x:x[1])

newG=[]
for i in range(N-1):
    now=Gx[i]
    next=Gx[i+1]
    dist=abs(now[0]-next[0])
    newG.append((dist,now[2],next[2]))

for i in range(N-1):
    now=Gy[i]
    next=Gy[i+1]
    dist=abs(now[1]-next[1])
    newG.append((dist,now[2],next[2]))

newG.sort()

uf=UnionFind(N)
count=N
ans=0
for c,i,j in newG:
    if count==0:
        break

    if not uf.same(i,j):
        ans+=c
        uf.union(i,j)
        count-=1

print(ans)