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

import re
s=input()
c=0
while "ABC" in s:
    t=re.subn("ABC","BCA",s)
    s=t[0]
    c+=t[1]
    lastA=s.rfind("A")
    #print(s,lastA)
    #print(s[lastA:(lastA + 3)])
    if not s[lastA:(lastA + 3)] == "ABC":
        s=s[:lastA]
    #print(s)
print(c)

### FIXED CODE ###

s=input()
i=1
new=[s[0]]
while i<len(s):
    if s[i]=="C" and s[i-1] == "B":
        new.pop()
        new.append("K")
    else:
        new.append(s[i])
    i+=1

cnt=0
ans=0
for i in range(len(new)-1,-1,-1):
    if new[i]=="A" and cnt > 0:
        ans+=cnt
    elif new[i]=="K":
        cnt+=1
    else:
        cnt=0
    
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
Cost = []
Key = []
for i in range(M):
    a, b = map(int, input().split())
    Cost.append(a)
    C_ = list(map(int, input().split()))
    C = 0
    for c in C_:
        C += (1 << (c - 1))
    Key.append(C)
ans = float('inf')
for i in range(1 << M):
    a = 0
    X = 0
    for j in range(M):
        if (i >> j) & 1 == 1:
            a += Cost[j]
            X |= Key[j]
    if X == 2 ** N - 1:
        ans = min(ans, a)

if ans == float('inf'):
    ans = -1
print(ans)




### FIXED CODE ###

N, M = map(int, input().split())
Cost = []
Key = []
for i in range(M):
    a, b = map(int, input().split())
    Cost.append(a)
    C_ = list(map(int, input().split()))
    C = 0
    for c in C_:
        C |= (1 << (c - 1))
    Key.append(C)
DP = [float('inf')] * (1 << N)
DP[0] = 0

for cost, key in zip(Cost, Key):
    D = DP[:]
    for i, d in enumerate(DP):
        if d == float('inf'):
            continue
        D[i|key] = min(D[i|key], d + cost)
    DP = D

if DP[-1] == float('inf'):
    print(-1)
else:
    print(DP[-1])
### BUGGY CODE ###

n = int(input())
res = 0
for i in range(1, n+1):
    res += (int(n / i) * (i + int(n / i) * i)) // 2
print(res)

### FIXED CODE ###

n = int(input())
res = 0
for i in range(1, n+1):
    res += (int(n / i) * (i + int(n / i) * i)) // 2
print(res)
### BUGGY CODE ###

A, B= map(int, input().split())
ans = 0
for i in range(A,B+1):
  ans= ans^i
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
ans = 0
for i in range(40):
    # 含まれる1の数を数える
    tmp = (B-A) // 2**(i+1) * 2**i
    p = A%(2**(i+1))
    q = (B-A)%(2**(i+1))
    # p から p+qの中で余りが2**i ~ 2**(i+1)-1になる個数を求める
    tmp += max(min(p+q,2**(i+1)-1) - max(p,2**i)+1,0)
    tmp += max(min(p+q,2**(i+1)-1 + 2**(i+1)) - max(p,2**i + 2**(i+1))+1,0)
    ans += (tmp%2) * 2**i
print(ans)
### BUGGY CODE ###

def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [None]*H
    Q = []
    for h in range(H):
        D[h] = [10e10]*W
        l = input().strip()
        for w in range(W):
            if l[w] == "#":
                D[h][w] = 0
                Q.append((0, h, w))

    m = 0
    while Q:
        d, h, w = heappop(Q)
        alt = d+1
        m = max(m, d)
        for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
            h1, w1 = h+dx, w+dy
            if 0 <= h1 < H and 0 <= w1 < W:
                if D[h1][w1] > alt:
                    D[h1][w1] = alt
                    heappush(Q, (alt, h1, w1))

    #for h in range(H): print(D[h])
    print(m)

main()




### FIXED CODE ###

def gen():
    print("1000 1000")
    print("#"+"."*999)
    for i in range(1000-1):
        print("."*1000)

def main():
    from collections import deque
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [None]*H
    Q = deque()
    for h in range(H):
        D[h] = [10e10]*W
        l = input()
        for w in range(W):
            if l[w] == "#":
                D[h][w] = 0
                Q.append((h, w))
    m = 0
    while Q:
        h, w = Q.popleft()
        alt = D[h][w] + 1
        for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
            h1, w1 = h+dx, w+dy
            if 0 <= h1 < H and 0 <= w1 < W:
                if D[h1][w1] > alt:
                    D[h1][w1] = alt
                    m = max(m, alt)
                    Q.append((h1, w1))

    print(m)
main()
### BUGGY CODE ###

import numpy as np

n = int(input())
A = np.array(list(map(int, input().split())))
q = int(input())

for i in range(q):
    a, b = map(int, input().split())
    A = np.where(A == a, b, A)
    print(A.sum())



### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())

S = sum(A)
dp = [0] * 100001
for a in A:
    dp[a] += 1


for i in range(q):
    a, b = map(int, input().split())
    dp[b] += dp[a]
    S = S + (b - a) * dp[a]
    print(S)
    dp[a] = 0
### BUGGY CODE ###

def sort_2(a,b):
    if b<a:
        c=a
        a=b
        b=c
    return [a,b]


def GCDbase(a,b):
    D=b//a
    if b==D*a:
        return a
    else:
        return GCD(b-a*D,a)
    
def GCD(a,b):
    ab=sort_2(a,b)
    return GCDbase(ab[0],ab[1])
    
    
def sort_3(a,b,c):
    if b<a:
        d=a
        a=b
        b=d
    if c<b:
        d=c
        c=b
        b=d
    if b<a:
        d=a
        a=b
        b=d
    return [a,b,c]

def gcd(a,b,c):
    abc=sort_3(a,b,c)
    a=abc[0]
    b=abc[1]
    c=abc[2]
    return GCD(GCD(a,b),c) 

K=int(input())
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            sum+=gcd(i,j,l)
print(sum)

### FIXED CODE ###

import math
K=int(input())
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp=math.gcd(i,j)
        for l in range(1,K+1):
            sum+=math.gcd(tmp,l)
print(sum)
### BUGGY CODE ###

mod = 10 ** 9 + 7

fact = [1]
fact_inv = [1]
for i in range(10 ** 6):
    new_fact = fact[-1] * (i + 1) % mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, mod - 2, mod))

def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] % mod

def solve():
    X, Y = map(int, input().split())
    if (2 * X - Y) % 3 == 0:
        s = (2 * Y - X) // 3
        t = (2 * X - Y) // 3
        ans = mod_comb_k(s + t, s, mod)
        print(ans)
    else:
        print(0)

solve()

### FIXED CODE ###

def mod_comb(n, k, p):
    if k > n - k:
        k = n - k
    
    numerator = 1
    denominator = 1
    for i, j in zip(range(n - k + 1, n + 1), range(1, k + 1)):
        numerator = (numerator * i) % p
        denominator = (denominator * j) % p
    
    return (numerator * pow(denominator, p - 2, p)) % p

def solve():
    mod = 10 ** 9 + 7
    X, Y = map(int, input().split())
    s = 2 * Y - X
    t = 2 * X - Y
    if s >= 0 and s % 3 == 0 and t >= 0 and t % 3 == 0:
        s //= 3
        t //= 3
        print(mod_comb(s + t, s, mod))
    else:
        print(0)

solve()
### BUGGY CODE ###

def check_val(ind):
    if ind > len(b): return False 
    if b[ind-1] == ind:
        ans.append(ind)
        del b[ind-1]
        return True
    else:
        return False


N,*b = map(int,open(0).read().split())
if b[0] != 1: 
    print(-1)
    exit()

set_b = sorted(set(b),reverse=True)
ans = []
while len(b) != 0:
    flg = False
    for i in set_b:
        flg = check_val(i)
        if flg: break
else: #消せるものがなくなった
    if len(b) == 0:
        print(*ans[::-1],sep="\n")
    else:
        print(-1)
    
    

### FIXED CODE ###

def check_val(ind):
    if ind > len(b): return False 
    if b[ind-1] == ind:
        ans.append(ind)
        del b[ind-1]
        if ind not in b: set_b.remove(ind)
        return True
    else:
        return False


N,*b = map(int,open(0).read().split())
if b[0] != 1: 
    print(-1)
    exit()

set_b = sorted(set(b),reverse=True)
ans = []

while len(b) != 0:
    flg = False
    for i in set_b:
        flg = check_val(i)
        if flg: break
    
    if flg == False:
        print(-1)
        exit() 
else: #消せるものがなくなった
    print(*ans[::-1],sep="\n")
### BUGGY CODE ###

from collections import Counter

n = int(input().strip())
A = [int(s) for s in input().strip().split()]
M = 10 ** 9 + 7

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

factors = Counter()
for a in A:
    d = Counter()
    while a % 2 == 0:
        d[2] += 1
        a //= 2
    for i in range(3, int(a ** 0.5) + 1, 2):
        while a % i == 0:
            d[i] += 1
            a //= i
        if a == 1:
            break
    if a > 1:
        d[a] += 1
    factors |= d
# print(factors)
m = 1
for k, v in factors.items():
    m = (m * pow(k, v, M)) % M

result = 0
for a in A:
    result = (result + m * modinv(a, M)) % M
print(result)

### FIXED CODE ###

n = int(input().strip())
A = [int(s) for s in input().strip().split()]
M = 10 ** 9 + 7

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

factors = [0] * 1001
large_factors = set()
for a in A:
    d = 0
    while a % 2 == 0:
        d += 1
        a //= 2
    factors[2] = max(factors[2], d)
    for i in range(3, int(a ** 0.5) + 1, 2):
        d = 0
        while a % i == 0:
            d += 1
            a //= i
        factors[i] = max(factors[i], d)
        if a == 1:
            break
    if a > 1000:
        large_factors.add(a)
    elif a > 1:
        factors[a] = max(factors[a], 1)

m = 1
for k, v in enumerate(factors):
    if v > 0:
        m = (m * pow(k, v, M)) % M
for k in large_factors:
    m = (m * k) % M

result = 0
for a in A:
    result = (result + m * modinv(a, M)) % M
print(result)
### BUGGY CODE ###

MOD = 10**9+7

N   = int(input())
A   = list(map(int,input().split()))
A2   = [0]*N
BitNum = [0]*(61)

for i in range(1,61):
    A2 = [0] * N
    for j in range(N):
        A2[j] = A[j] % 2
        A[j] //= 2
    BitNum[i] = sum(A2)

ans = 0
beki = 0
for i in range(1,61):
    x = BitNum[i]
    y = N - x
    ans += (x*y)*(2**beki)
    ans %= MOD
    beki += 1
print(ans)


### FIXED CODE ###

MOD = 10**9+7

N   = int(input())
A   = list(map(int,input().split()))
A2   = [0]*N
BitNum = [0]*(61)

for i in range(1,61):
    A2 = [0] * N
    for j in range(N):
        A2[j] = A[j] % 2
        A[j] //= 2
    BitNum[i] = sum(A2)

ans = 0
beki = 0
for i in range(1,61):
    x = BitNum[i]
    y = N - x
    ans += (x*y)*(2**beki)
    ans %= MOD
    beki += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
DD = [i+j for i in A for j in B]
DD.sort()
F = [(i+j)
     for i in DD[max(len(DD)-3002,0):]
     for j in C
]
F.sort()
for i in range(K):
    print(F[-1-i])
        


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline
X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
DD = [i+j for i in A for j in B]
DD.sort()
heap = []
for i in DD[max(len(DD)-3001,0):]:
     for j in C:
         heapq.heappush(heap,-(i+j))
for i in range(K):
    print(-heapq.heappop(heap))
### BUGGY CODE ###

N = int(input())
T, A = 0, 0
for i in range(N):
    Ti, Ai = map(int, input().split())
    t, a = Ti, Ai
    while t < T or a < A:
        t += Ti
        a += Ai
    T, A = t, a
print(T + A)


### FIXED CODE ###

N = int(input())
T, A = map(int, input().split())
for i in range(N - 1):
    Ti, Ai = map(int, input().split())
    mt = T // Ti + (1 if T % Ti > 0 else 0)
    ma = A // Ai + (1 if A % Ai > 0 else 0)
    m = max(mt, ma)
    Ti *= m
    Ai *= m
    T, A = Ti, Ai
print(T + A)
### BUGGY CODE ###

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]
ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]

for i in range(Q):
    l,r = lr_list[i][0]-1, lr_list[i][1]-1
    ans = sum(ac_tf_list[l:r])
    print(ans)


### FIXED CODE ###

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]

# ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
t = [0]*N
for i in range(N-1):
    if S[i:i+2]=='AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l = lr_list[i][0]-1
    r = lr_list[i][1]-1
    print(t[r]-t[l])
### BUGGY CODE ###

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

h = int(m/n)+1
x = 0
for a in range(h, 0, -1):
    if m>=a*n and m%a == 0:
        print(a)
        break

### FIXED CODE ###

import sys

def make_divisors(num):
    divisors = []
    for i in range(1, int(num**0.5)+1):
        if num%i == 0:
            divisors.append(i)
            if num//i != i:
                divisors.append(num//i)
    divisors.sort()
    return divisors

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

divisors = make_divisors(m)

for i in range(1, len(divisors)+1):
    if divisors[i*-1] * n <= m:
        print(divisors[i*-1])
        sys.exit()
### BUGGY CODE ###

from heapq import heappop, heappush

INF = 10 ** 20

xs, ys, xt, yt = map(int, input().split())
N = int(input())
circle = [list(map(int, input().split())) for _ in range(N)]
circle = [[xs, ys, 0]] + circle + [[xt, yt, 0]]
edges_lst = [[] for _ in range(N + 2)]
dist_lst = [INF] * (N + 2)
for i, (x1, y1, r1) in enumerate(circle):
    for j, (x2, y2, r2) in enumerate(circle[i + 1:]):
        j += i + 1
        d = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** .5
        dist = d - r1 - r2
        if d - r1 - r2 > 0:
            edges_lst[i].append((j, dist))
            edges_lst[j].append((i, dist))
        else:
            edges_lst[i].append((j, 0))
            edges_lst[j].append((i, 0))


que = []
heappush(que, (0, 0))
dist_lst[0] = 0
while que:
    dist, node = heappop(que)
    for to, cost in edges_lst[node]:
        if dist_lst[to] > cost + dist:
            dist_lst[to] = cost + dist
            heappush(que, (cost + dist, to))

print('{:.10f}'.format(dist_lst[-1]))

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

INF = 10 ** 20

xs, ys, xt, yt = map(int, input().split())
N = int(input())
X = np.zeros((1, N + 2), dtype=np.float64)
Y = np.zeros((1, N + 2), dtype=np.float64)
R = np.zeros((1, N + 2), dtype=np.float64)

X[0][0] = xs
Y[0][0] = ys
X[0][N + 1] = xt
Y[0][N + 1] = yt

for i in range(N):
    X[0][i + 1], Y[0][i + 1], R[0][i + 1] = map(int, input().split())

# G[i][j]: iからjまでの距離
G = np.maximum(np.sqrt(np.square(X - X.T) + np.square(Y - Y.T)) - (R + R.T),
               np.zeros((N + 2, N + 2), dtype=np.float64))
# 対角行列をinfで塗りつぶす
G += np.diag(np.ones(N + 2, dtype=np.float64) * np.inf)
# 自己ループを消す
G = csgraph_from_dense(G, null_value=np.inf)
print(dijkstra(G, indices=0)[-1])
### BUGGY CODE ###

n = input()

a, b = n.split()

a = int(a)
b = int(b)

flag = False
for i in range(a):
    if flag:
        break
    for j in range(b):
        if (((i+1) * (j+1)) % a) == 0 and (((i+1) * (j+1)) % b) == 0:
            print((i+1) * (j+1))
            flag = True
            break


### FIXED CODE ###

n = input()

a, b = n.split()

a = int(a)
b = int(b)

for i in range(10 ** 5):
    i = i + 1
    if (i * a) % b == 0:
        print(a*i)
        break
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        a = L[i]+L[j]
        l = len(L[j+1:])
        b = l-bisect.bisect_left(L[j+1:],a)
        cnt+=l-b
print(cnt)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        b = bisect.bisect_left(L,L[i]+L[j])
        cnt += b-j-1
print(cnt)
### BUGGY CODE ###

s = list(input())
flag = True
cnt=0

while flag:
    flag = False
    n = len(s)
    for i in range(n-1):
        k = s[i]+s[i+1]
        if (k=="01") or (k=="10"):
            del(s[i:i+2])
            flag = True
            cnt+=1
            break

print(cnt*2)

### FIXED CODE ###

s = list(input())

print(min(s.count("0"),s.count("1"))*2)
### BUGGY CODE ###

MAX_INT = int(10e10)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

R,G,B,N = IL()

cnt = 0
num = N
for i in range(0,N+1,R):
    tmp = num - i
    for j in range(0,N+1,G):
        tmp2 = tmp - j
        if tmp2%B == 0 and tmp2 >= 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0
num = N
for i in range(0,N+1,R):
    tmp = num - i
    for j in range(0,N+1,G):
        tmp2 = tmp - j
        if tmp2%B == 0 and tmp2 >= 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
ans = 0
nums = list(map(int, input().split()))
for i in range(n):
    for l in range(n):
        if(i!=l and abs(l-i) == nums[i]+nums[l]):
            ans += 1
print(ans//2)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
vals = []
mappy = {}
ans = 0
for i in range(n):
    if(i+1-a[i] > 0):
        if(i+1-a[i] in mappy):
            mappy[i+1-a[i]]+=1
        else:
            mappy[i+1-a[i]] =1
for i in range(n):
    if(i+1+a[i]in mappy):
        ans+=mappy[i+1+a[i]]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC121 D

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

s = A
for i in range(A+1,B+1):
    s = s^i
print(s)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC121 D

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

if A % 2 == 0 and B % 2 == 0:
    s = 1
elif A % 2 == 0 and B % 2 == 1:
    s = 2
elif A % 2 == 1 and B % 2 == 0:
    s = 3
elif A % 2 == 1 and B % 2 == 1:
    s = 4
if s == 1:
    if ((B - A)/2) % 2 == 1:
        print(1^B)
    else:
        print(0^B)
elif s == 2:
    if ((B - A+1)/2) % 2 == 1:
        print(1)
    else:
        print(0)
elif s == 3:
    if ((B - A-1)/2) % 2 == 1:
        print(A^1^B)
    else:
        print(A^B)
else:
    if ((B - A)/2) % 2 == 1:
        print(A^1)
    else:
        print(A^0)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(S[l-1:r].count('AC'))

print('\n'.join(list(map(str, ans))))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]

ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(cnt[r-1] - cnt[l-1])

print('\n'.join(list(map(str, ans))))
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
import sys
for i in range(N):
    if i > 0:
        if H[i-1] > H[i]:
            if max(H[:i]) > H[i]+1:
                print("No")
                sys.exit()
print("Yes")

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
max_H = 0
import sys
for i in range(N):
    if max_H > H[i]+1:
        print("No")
        sys.exit()
    if max_H < H[i]:
        max_H = H[i]
print("Yes")
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(n):
  s.append("".join(sorted(input())))
s.sort()
sss=set(s)
ans=0
for _ in sss:
  l=s.count(_)
  ans+=l*(l-1)//2
print(ans)


### FIXED CODE ###

n=int(input())
s=[]
for i in range(n):
  s.append("".join(sorted(input())))
#sss=set(s)
ans=0
import collections
c=collections.Counter(s)

for l in c.values():
  ans+=l*(l-1)*(1/2)
print(int(ans))
### BUGGY CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

### FIXED CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import gcd, ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
c = 0
K = INT()
ans = 0
 
for i in range(1, K + 1):
    for j in range(1, K + 1):
        a = gcd(i, j)
        for k in range(1, K + 1):
            b = gcd(a, k)
            ans += b
print(ans)            

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import gcd, ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
# from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

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


exit()
q = [[str(i)] for i in range(1, K+1)]
# print(q)
s = []
ans = 0
while q:
    a = q.pop()
    # print(q)@
    if len(a) == 3:
        # s.append(a)
        ans += int(a[-1])
        # print(a)
    else:
        for i in range(1, K+1):
            b = deepcopy(a)
            if int(b[-1]) <= i:
                b.append(b[-1])
            # b += str(gcd(i, int(b[-1])))
            else:
                b.append(str(i))
            q.append(b)
print(ans)
# print(s)
# print(s)
# ans = 0
# for d in s:
#     print(sorted(list(d))[0])

# print(ans)