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

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N=I()
    A=LI()
    MA=max(A)
    x=[0]*(MA+1)
    
    #数列x[i]はi*(iの個数)
    for i in range(N):
        x[A[i]]+=A[i]
        
    #print(x)
    
    #上位集合のゼータ変換
    for k in range(1,MA+1):
        for s in range(k*2,MA+1,k):#sが2kからkずつ増える=>sはkの倍数(自分自身を数えないため，2kから)
            x[k]=(x[k]+x[s])%mod
    
    #print(x)
    #この段階でx[i]はiを約数に持つやつの和(個数も加味している)
    
    #積演算
    for i in range(MA+1):
        x[i]=(x[i]*x[i])%mod
        
    #print(x)
    
    
    #メビウス変換で戻す
    for k in range(MA,0,-1):
        for s in range(k*2,MA+1,k):
            x[k]=(x[k]-x[s])%mod
            
    #この段階でx[i]はiをgcdに持つもの同士をかけたものの和
    #print(x)
    
    #gcdでわる
    for i in range(2,MA+1):
        x[i]=(x[i]*pow(i,mod-2,mod))%mod
        
    #この段階でx[i]はiをgcdに持つもの同士のlcaの和
    #print(x)
    
    """
    for i in range(MA+1):
        if x[i]!=0:
            print(i,x[i])"""
    
    
    ans=(sum(x))%mod
    #xの和を取るa
        
    ans=(ans-sum(A))%mod
    #A[i],A[i]の組を除去する．A[i]動詞のくみはlcaがA[i]になる
       
    """ 
    ans=(ans*pow(2,mod-2,mod))%mod#A[i]*A[j] と　A[j]*A[i]の被り除去
    print(pow(2,mod-2,mod))=499122177
    """
    ans=(ans*499122177)%mod
    
    print(ans)
        
    
    

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N=I()
    A=LI()
    MA=max(A)
    x=[0]*(MA+1)
    
    #数列x[i]はi*(iの個数)
    for i in range(N):
        x[A[i]]+=A[i]
        
    #print(x)
    
    #上位集合のゼータ変換
    for k in range(1,MA+1):
        for s in range(k*2,MA+1,k):#sが2kからkずつ増える=>sはkの倍数(自分自身を数えないため，2kから)
            x[k]=(x[k]+x[s])%mod
    
    #print(x)
    #この段階でx[i]はiを約数に持つやつの和(個数も加味している)
    
    #積演算
    for i in range(MA+1):
        x[i]=(x[i]*x[i])%mod
        
    #print(x)
    
    
    #メビウス変換で戻す
    for k in range(MA,0,-1):
        for s in range(k*2,MA+1,k):
            x[k]=(x[k]-x[s])%mod
            
    #この段階でx[i]はiをgcdに持つもの同士をかけたものの和
    #print(x)
    
    #gcdでわる
    ans=0
    for i in range(1,MA+1):
        if x[i]!=0:
            x[i]=(x[i]*pow(i,mod-2,mod))%mod
            ans=(ans+x[i])%mod
        
    #この段階でx[i]はiをgcdに持つもの同士のlcaの和
    #print(x)
        
    ans=(ans-sum(A))%mod
    #A[i],A[i]の組を除去する．A[i]動詞のくみはlcaがA[i]になる
       
    """ 
    ans=(ans*pow(2,mod-2,mod))%mod#A[i]*A[j] と　A[j]*A[i]の被り除去
    print(pow(2,mod-2,mod))=499122177
    """
    ans=(ans*499122177)%mod
    
    print(ans)
        
    
    

main()
### BUGGY CODE ###

import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
tree=[[] for _ in range(N)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  tree[u-1].append((v-1,w))
  tree[v-1].append((u-1,w))
ans=[-1]*N
ans[0]=0
d=deque([0])
done=[0]
while d:
  p=deque.popleft(d)
  color=ans[p]
  for v,w in tree[p]:
    if not v in done:
      deque.append(d,v)
      done.append(v)
      ans[v]=color^(w%2)
print(*ans,sep='\n')

### FIXED CODE ###

import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
tree=[[] for _ in range(N)]
for _ in range(N-1):
  u,v,w=map(int,input().split())
  tree[u-1].append((v-1,w))
  tree[v-1].append((u-1,w))
ans=[-1]*N
ans[0]=0
d=deque([0])
while d:
  p=deque.popleft(d)
  color=ans[p]
  for v,w in tree[p]:
    if ans[v]==-1:
      deque.append(d,v)
      ans[v]=color^(w%2)
print(*ans,sep='\n')
### BUGGY CODE ###

N = int(input())
P = list(map(float, input().split()))
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1.0
for i in range(1, N + 1):
    for j in range(N):
        if j < N:
            dp[i][j + 1] += dp[i - 1][j] * P[i - 1]
        dp[i][j] += dp[i - 1][j] * (1 - P[i - 1])

num = 0
for i in range(N + 1):
    if i > N // 2:
        num += dp[N][i]

print(num)


### FIXED CODE ###

N = int(input())
P = list(map(float, input().split()))
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1.0
for i in range(1, N + 1):
    for j in range(N):
        if j < N:
            dp[i][j + 1] += dp[i - 1][j] * P[i - 1]
        dp[i][j] += dp[i - 1][j] * (1 - P[i - 1])

num = 0
for i in range(N + 1):
    if i > N // 2:
        num += dp[N][i]

print(num)
### BUGGY CODE ###

n = int(input())

a = tuple(map(int, input().split()))
cnt = 0
for i in range(1,n):
    for j in range(i+1,n+1):
        if a[i-1]+a[j-1] == j-i:
            cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
a = tuple(map(int, input().split()))

plus = {}
minus = {}
for i in range(n):
    p = i + 1 + a[i]
    m = i + 1 - a[i]
    if p not in plus:
        plus[p] = 0
    if m not in minus:
        minus[m] = 0
    plus[p] += 1
    minus[m] += 1

cnt = 0
for i in plus.keys():
    if i in minus:
        cnt += plus[i]*minus[i]

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

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p, s = [], []
cor, pen = 0, 0
for _ in range(m):
    li = input().split()
    p.append(int(li[0]))
    s.append(li[1])
for j in range(n):
    corFlag = False
    penCnt = 0
    for i in range(m):
        if (p[i] == j + 1):
            if corFlag:
                continue
            elif (s[i] == 'WA'):
                penCnt += 1
            else:
                cor += 1
                corFlag = True
    if corFlag:
        pen += penCnt
print(cor, pen)

### FIXED CODE ###

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

hasAC, pena, tmpP= [0] * n, [0] * n, [0] * n

for i in range(m):
    li = input().split()
    p = int(li[0]) - 1
    s = li[1]
    if hasAC[p]:
        continue
    if s == 'AC':
        hasAC[p] = 1
        pena[p] += tmpP[p]
    else:
        tmpP[p] += 1

print(sum(hasAC), sum(pena))
### BUGGY CODE ###

N = int(input())
C = dict()
i, cp, r = 0, 0, ['x'] * N
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            r[C[c]] = i
        C[c], cp = i, c
        i += 1
length = i
hist, add, ans = [0] * length, [0] * length, 0
for l in range(length):
    hist[l] = hist[l-1] + add[l]    
    if r[l] != 'x':
        add[r[l]] += hist[l] + 1
        ans += hist[l] + 1
print((ans+1) % (10**9+7))

### FIXED CODE ###

N = int(input())
C = dict()
i, cp, hist, ans = 0, 0, [0]*N, 0
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            temp = hist[C[c]] + 1
            hist[i] = hist[i-1] + temp
            ans += temp
        else:
            hist[i] += hist[i-1]
        C[c], cp = i, c
        i += 1
print((ans+1) % (10**9+7))
### BUGGY CODE ###

import heapq
#Aの中でa番目、Bの中でb番目、Cの中でc番目のものがabc > Kの時、大きい順のK番目以内にabcの組が入ることはない
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

h = []
check = [[[0] * Z for _ in range(Y)] for _ in range(X)]
heapq.heappush(h, [-(A[0]+B[0]+C[0]), 0, 0, 0])
check[0][0][0] = 1
for count in range(K):
    ans = heapq.heappop(h)
    i, j , k = ans[1], ans[2], ans[3]
    print (-ans[0])
    if i + 1 < X:
        if check[i+1][j][k] == 0:
            heapq.heappush(h, [-(A[i+1]+B[j]+C[k]), i+1, j, k])
            check[i+1][j][k] = 1
    if j + 1 < Y:
        if check[i][j+1][k] == 0:
            heapq.heappush(h, [-(A[i]+B[j+1]+C[k]), i, j+1, k])
            check[i][j+1][k] = 1
    if k + 1 < Z:
        if check[i][j][k+1] == 0:
            heapq.heappush(h, [-(A[i]+B[j]+C[k+1]), i, j, k+1])
            check[i][j][k+1] = 1
    

### FIXED CODE ###

#単純な全探索-->TLE-->Cの配列を扱うときに工夫
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

lst = []
for i in A:
    for j in B:
        lst += [i + j]

lst.sort(reverse = True)
C.sort(reverse = True)

ans = []
for i in range(min(K, len(lst))):
    for j in range(min(K, len(C))):
        ans += [lst[i]+C[j]]

ans.sort(reverse = True)
for i in range(K):
    print (ans[i])
### BUGGY CODE ###

from math import gcd
n = int(input())
a, b, c = 1, 1, 1
sum = 0
while True:
    sum += gcd(gcd(a, b), c)
    if n > c:
        c += 1
    elif n == c and n == b and n == a:
        break
    elif n == c and n == b:
        a += 1
        b = 1
        c = 1
    elif n == c:
        b += 1
        c = 1
print(sum)

### FIXED CODE ###

from math import gcd
n = int(input())
sum = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(gcd(i, j), k)
print(sum)
### BUGGY CODE ###

# C - Grid Repainting 2
from collections import deque

H, W = map(int, input().split())
grid = [[''] * W for _ in range(H)]
for i in range(H):
    grid[i] = list(str(input()))

d = deque()
ans = 'Yes'
for i in range(H):
    for j in range(W):
        d.append((i, j))
        tmp = 0
        while d:
            p, q = d.popleft()
            if grid[p][q] == '#':
                grid[p][q] = '.'
                tmp += 1
            for x, y in ((0, 1), (1, 0), (1, 0), (0, -1)):
                nx = p+x
                ny = q+y
                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    continue
                if grid[nx][ny] == '.':
                    continue
                d.append((nx, ny))
        if tmp == 1:
            ans = 'No'
            break
    else:
        continue
    break
print(ans)

### FIXED CODE ###

# C - Grid Repainting 2
from collections import deque

H, W = map(int, input().split())
grid = [[''] * W for _ in range(H)]
for i in range(H):
    grid[i] = list(str(input()))

d = deque()
ans = 'Yes'
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            continue
        d.append((i, j))
        grid[i][j] = '.'
        tmp = 1
        while d:
            p, q = d.popleft()
            for x, y in ((0, 1), (1, 0), (-1, 0), (0, -1)):
                nx = p+x
                ny = q+y
                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    continue
                if grid[nx][ny] == '.':
                    continue
                d.append((nx, ny))
                grid[nx][ny] = '.'
                tmp += 1
        if tmp == 1:
            ans = 'No'
            break
    else:
        continue
    break
print(ans)
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(1,n):
  ans += i % (i+1)
print(ans)

### FIXED CODE ###

n = int(input())
print((n * (n-1)) // 2)
### BUGGY CODE ###

s = input()
q = int(input())
rev = 1
for i in range(q):
  t = input()
  
  if t == '1':
    rev *= -1
  else:
    x,y,sr = t.split()
    if (rev == 1 and y == '2') or (rev == -1 and y == '1'):
      s = s + sr
    else:
      s = sr + s

if rev == -1:
  s = s[::-1]
  
print(s)  
  

### FIXED CODE ###

from collections import deque
que1 = deque([])
que2 = deque([])
s = input()
q = int(input())
rev = 1
for i in range(q):
  t = input()
  
  if t == '1':
    rev *= -1
  else:
    x,y,sr = t.split()
    if (rev == 1 and y == '2') or (rev == -1 and y == '1'):
      que2.append(sr)
    else:
      que1.appendleft(sr)

s = ''.join(que1+deque([s])+que2)     
if rev == -1:
  s = s[::-1]
  
print(s)
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 10**9+7
data = [[] for j in range(n+1)]
done = [0]*(n+1)
colors = [k-1]*(n+1)

for i in range(n-1):
  a, b = map(int, input().split())
  data[min(a,b)].append(max(a,b))
  data[max(a,b)].append(min(a,b))

queue = [1]
ans = 1
colors[1] += 1
for d in data[1]:
  colors[d] += 1
while queue != []:
  idx = queue.pop(0)
  done[idx] = 1
  ans *= colors[idx]
  ans %= mod
  cnt = 0
  for i in range(len(data[idx])):
    if done[data[idx][i]]:
      continue
    cnt += 1
    colors[data[idx][i]] -= cnt
    queue.append(data[idx][i])

print(ans)
  
  

### FIXED CODE ###

n, k = map(int, input().split())
mod = 10**9+7
data = [[] for j in range(n+1)]
done = [0]*(n+1)
colors = [k-1]*(n+1)

for i in range(n-1):
  a, b = map(int, input().split())
  data[min(a,b)].append(max(a,b))
  data[max(a,b)].append(min(a,b))

queue = [1]
ans = 1
colors[1] += 1
for d in data[1]:
  colors[d] += 1
while queue != []:
  idx = queue.pop(0)
  done[idx] = 1
  ans *= colors[idx]
  ans %= mod
  cnt = 0
  for i in range(len(data[idx])):
    if done[data[idx][i]]:
      continue
    cnt += 1
    colors[data[idx][i]] -= cnt
    queue.append(data[idx][i])

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

n = int(input())
array = list(map(int,input().split(' ')))

def getSum(s, e):
    sum = 0
    for i in range(s, e):
        sum = sum + array[i]
    return sum

prev = 0
for i in range(0,n-1):
    diff = abs(getSum(0, i+1) - getSum(i+1, n))
    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)





### FIXED CODE ###

n = int(input())
array = list(map(int,input().split(' ')))

left= array[0]
right = sum(array) - left

prev = 0
for i in range(0,n-1):
    diff = abs(left - right)
    left = left + array[i+1]
    right = right - array[i+1]

    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)
### BUGGY CODE ###

S = input()
count =0

while True:
    if '01' not in S and '10' not in S:
        break
    if '01' in S:
        S = S.replace('01','',1)
        count += 1
        #print(S)
    if '10' in S:
        S = S.replace('10','',1)
        count += 1
        #print(S)

#print(S)
print(count*2)

### FIXED CODE ###

S = input()

a = S.count('0')
b = S.count('1')

print(a+b-abs(a-b))
### BUGGY CODE ###

class Acc2D:
    def __init__(self, a, K):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)
        self.K = K

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                # 末項は必要に応じて改変すること
        return ret

    def get(self, r1, r2, c1, c2):
        # [r1,r2), [c1,c2) : 0-indexed
        if r1 < 0: r1 = 0
        if r2 >= self.K * 2: r2 = self.K * 2
        if c1 < 0: c1 = 0
        if c2 >= self.K * 2: c2 = self.K * 2
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys
    input = sys.stdin.readline

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

    g = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        x, y, c = input().split()
        x = int(x) % (K * 2)
        y = (int(y) - (K if c == 'B' else 0)) % (K * 2)
        g[x][y] += 1  # White

    acc2d = Acc2D(g, K)
    ans = -1
    for r in range(K):
        for c in range(K):
            t = acc2d.get(0, r, 0, c)
            t += acc2d.get(0, r, c + K, c + K * 2)
            t += acc2d.get(r, r + K, c, c + K)
            t += acc2d.get(r + K, r + K * 2, 0, c)
            t += acc2d.get(r + K, r + K * 2, c + K, c + K * 2)
            ans = max(ans, t, N - t)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()


### FIXED CODE ###

# https://atcoder.jp/contests/abc086/submissions/3454297

def main():
    import sys

    input = sys.stdin.readline

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

    grid = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        col, row, color = input().split()
        col = int(col)
        row = int(row)
        if color == 'W':
            row += K
            # Bに統一
        row %= K * 2
        col %= K * 2
        grid[row][col] += 1

    tbl = [[0] * (K * 2 + 1) for _ in range(K * 2 + 1)]
    for row in range(K * 2):
        for col in range(K * 2):
            tbl[row + 1][col + 1] = tbl[row + 1][col] + tbl[row][col + 1] - tbl[row][col] + grid[row][col]

    def count(row, col, row2, col2):
        return tbl[row2][col2] - tbl[row][col2] - tbl[row2][col] + tbl[row][col]

    ret = 0
    for row in range(K):
        for col in range(K):
            tmp = (
                    count(0, 0, row, col)
                    + count(row, col, row + K, col + K)
                    + count(row + K, col + K, K * 2, K * 2)
                    + count(row + K, 0, K * 2, col)
                    + count(0, col + K, row, K * 2)
            )
            ret = max(ret, tmp, N - tmp)
            # xox
            # oxo
            # xox
            # x=tmp
            # o=N-tmp

    print(ret)


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

N,M,K = map(int, input().split())

mod = 10**9+7
a = 1
b = 1
for i in range(min(K-2, N*M-K)):
    a *= (N*M-2-i)
    b *= i+1

comb = a//b
ans = ((N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2 + (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2)%mod
ans *= comb
print(ans%mod)

### FIXED CODE ###

N,M,K = map(int, input().split())

mod = 10**9+7
a = 1
b = 1
for i in range(min(K-2, N*M-K)):
    a *= (N*M-2-i)
    a %= mod
    b *= i+1
    b %= mod
comb = a * pow(b, mod - 2, mod) % mod

ans = (((N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2 + (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2)*comb)%mod
print(ans)
### BUGGY CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

"""
S = "s0 s1 ... s(N-1)"に対して"sl s(l+1) ... s(r-1)"が素数Pで割り切れるかを考える。
これはa_i := int("si s(i+1) ... s(N-1)")と定めることで、
    (a_l - a_r) / 10^{N-r} ¥cong 0  (mod P)
と定式化できる。

（整数関連の区間の問題は後ろからの累積和が相性良さそう。頭からの累積を考えたのが敗因な気がする）

Pが2でも5でもない場合は、上式は
    a_l - a_r ¥cong 0 (mod P)
に同値であるから、各a_iのmod Pでの値を辞書にまとめておけば良さそう。
Pが2, 5のいずれかの場合は偶然チェックが簡単なので解ける。
"""

ans = 0
if P == 2:
    for i in range(N):
        a = int(S[i])
        if a % 2 == 0:
            ans += i + 1
elif P == 5:
    for i in range(N):
        a = int(S[i])
        if a == 0 or a == 5:
            ans += i + 1
else:
    S += "0" # 上の定式化の都合上、r = Nのケースが必要なので
    res = [0] * P
    for i in range(N + 1):
        a = int(S[i:]) % P
        res[a] += 1

    for r in res:
        ans += r * (r - 1) // 2

print(ans)


### FIXED CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

"""
S = "s0 s1 ... s(N-1)"に対して"sl s(l+1) ... s(r-1)"が素数Pで割り切れるかを考える。
これはa_i := int("si s(i+1) ... s(N-1)")と定めることで、
    (a_l - a_r) / 10^{N-r} ¥cong 0  (mod P)
と定式化できる。

（整数関連の区間の問題は後ろからの累積和が相性良さそう。頭からの累積を考えたのが敗因な気がする）

Pが2でも5でもない場合は、上式は
    a_l - a_r ¥cong 0 (mod P)
に同値であるから、各a_iのmod Pでの値を辞書にまとめておけば良さそう。
Pが2, 5のいずれかの場合は偶然チェックが簡単なので解ける。
"""

ans = 0
if P == 2:
    for i in range(N):
        a = int(S[i])
        if a % 2 == 0:
            ans += i + 1
elif P == 5:
    for i in range(N):
        a = int(S[i])
        if a == 0 or a == 5:
            ans += i + 1
else:
    S += "0" # 上の定式化の都合上、r = Nのケースが必要なので
    d = defaultdict(int)
    r = 0
    d[0] += 1
    for i in range(N - 1, -1, -1):
        """
        ここでS[i:]を毎回Pで割るとTLEする（桁の大きい演算はやはり負担が大きいのか？）
        (a_i % P)をi = N, N-1,...の降順に求めていくことを考えれば、
        前の計算結果が使える、特に繰り返し二乗法が使えるのでだいぶ早くなるみたい。
        """
        r += int(S[i]) * pow(10, N - i - 1, P)
        r %= P
        d[r] += 1

    for num in d.values():
        ans += num * (num - 1) // 2

print(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:
			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)

### 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 ###

from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


n = int(input())
a = list(map(int, input().split()))
arr = [0] * (2 * 10 ** 5 + 1)

for i in a:
    arr[i] += 1

for i in a:
    arr[i] -= 1
    ans = 0
    for j in arr:
        if j > 1:
            ans += combinations_count(j, 2)
    arr[i] += 1

    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = (2 * 10 ** 5) + 1
b = [0] * l


def nC2(n):
    return n * (n - 1) // 2


for i in range(n):
    b[a[i]] += 1

ttl = 0
for j in range(l):
    ttl += b[j] * (b[j] - 1) // 2

for k in range(n):
    print(ttl - nC2(b[a[k]]) + nC2(b[a[k]] - 1))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf') for i in range(N)]

dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(1, N):
  for j in range(1, min(K+1, i+1)):
    dp[i] = min(dp[i-j] + abs(h[i] - h[i-j]), dp[i])

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf') for i in range(N)]

dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(1, N):
  for j in range(1, min(K+1, i+1)):
    dp[i] = min(dp[i-j] + abs(h[i] - h[i-j]), dp[i])

print(dp[N-1])
### BUGGY CODE ###

isPrime = [True for i in range(100001)]
isPrime[0] = False
isPrime[1] = False

for i in range(2, 100001):
    if isPrime[i]:
        j = 2
        while i*j <= 100000:
            isPrime[i*j] = False
            j += 1

q = int(input())
que = list()
for i in range(q):
    que.append(list(map(int, input().split())))

for a, b in que:
    ans = 0
    for i in range(a, b+1):
        if isPrime[i]:
            if isPrime[(i+1)//2]:
                ans += 1
    print(ans)


### FIXED CODE ###

isPrime = [True for i in range(100001)]
isPrime[0] = False
isPrime[1] = False

for i in range(2, 100001):
    if isPrime[i]:
        j = 2
        while i*j <= 100000:
            isPrime[i*j] = False
            j += 1

isSimilar = [True for i in range(100001)]
for i in range(100001):
    if isPrime[i] and isPrime[(i+1)//2]:
        pass
    else:
        isSimilar[i] = False

cnt = [0 for i in range(1, 100010)]
for i in range(1, 100001):
    cnt[i] = cnt[i-1] + [0, 1][isSimilar[i]]

q = int(input())
lrs = list()
for i in range(q):
    lrs.append(list(map(int, input().split())))

for l, r in lrs:
    print(cnt[r]-cnt[l-1])