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

# -*- coding: utf-8 -*-

import sys
import os

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(2, N // i + 1):
            index = i * j
            if index < N:
                lst[i * j] = False

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break

    if n % 2 == 1:
        if lst[n - 2]:
            print(1)
        else:
            print(0)
    elif n == 4:
        print(1)
    else:
        counter = 0
        for i in range(1, n // 2 + 1, 2):
            prime0 = i
            prime1 = n - i
            if prime0 <= prime1 and lst[prime0] and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)

### FIXED CODE ###

import sys

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(i * i, N, i):
            lst[j] = False

primes = [i for i in range(1, N) if lst[i]]

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print(1)
        else:
            print(0)
    elif n == 4:
        print(1)
    else:
        counter = 0
        for prime0 in primes:
            prime1 = n - prime0
            if prime0 <= prime1 and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    
    BL = (300000).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
    
    # TODO: default value
    buf = [0] * BUFSIZE
    
    def update(i, x):
        i += BASE
        buf[i] = x
        i = (i-1) // 2
        while i >= 0:
            buf[i] = compare(buf[2*i+1], buf[2*i+2])
            i = (i-1) // 2
    
    # [q_left, q_right]
    def search(q_left, q_right):
        return _search(0, WIDTH, 0, q_left, q_right)
    
    def _search(l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return 0
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
        c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return compare(c1, c2)
    
    def compare(i1, i2):
        if i1 > i2:
            return i1
        else:
            return i2
    
    for _ in range(N):
        a = int(input().rstrip())
        maxlen = search(a-K, a+K)
        update(a, maxlen+1)
    print(search(0, 300000))

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())

BL = (300001-1).bit_length()
WIDTH = pow(2, BL)
BUFSIZE = pow(2, BL+1) - 1
BASE = BUFSIZE - WIDTH
DEFAULT = 0

buf = [DEFAULT] * BUFSIZE

def update(i, x):
    i += BASE
    buf[i] = x
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2

# [q_left, q_right]
def search(left, right):
    ansl = ansr = DEFAULT
    left += BASE
    right += BASE
    while left < right:
        if not (left & 1):
            ansl = compare(ansl, buf[left])
            left += 1
        if right & 1:
            ansr = compare(ansr, buf[right])
            right -= 1
        left = (left-1) // 2
        right = (right-1) // 2
    if left == right:
        ansl = compare(ansl, buf[left])
    return compare(ansl, ansr)

def compare(v1, v2):
    return v1 if v1 > v2 else v2

for _ in range(N):
    a = int(input().rstrip())
    maxlen = search(max(0, a-K), min(a+K, 300000))
    update(a, maxlen+1)
print(search(0, 300000))
### BUGGY CODE ###

N = int(input())
l_list = sorted(map(int,input().split()))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if l_list[i]+l_list[j] > l_list[k]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
l_list = sorted(map(int,input().split()))
ans = 0
#print(l_list)
for i in range(N):
    for j in range(i+1,N):
        sum_ij = l_list[i]+l_list[j]
        bi_num = bisect.bisect_left(l_list,sum_ij)
        #print(i,j,sum_ij,bi_num,bi_num-j)
        ans += bi_num-j-1
print(ans)
### BUGGY CODE ###

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

a = [input().split() for i in range(m)]
c = []
d = []
for i in range(m):
    
    if int(a[i][0]) == 1:
        c.append(int(a[i][1]))
    elif int(a[i][1]) == n:
        d.append(int(a[i][0]))
ans = False
c = list(set(c))
for i in c:
    if d.count(i) >=1:
        ans = True
        break
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]

for i in range(m):
    a[i],b[i] = map(int,input().split())

go = []
goal = []

for i in range(len(a)):
    if a[i] == 1:
        go.append(b[i])
    if b[i] == n:
        goal.append(a[i])

count = [0 for i in range(n)]
for i in range(len(go)):
    count[go[i]-1] = 1
for i in range(len(goal)):
    count[goal[i]-1] += 1
for i in range(len(count)):
    if count[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

from operator import itemgetter
from heapq import heappush,heappop
import sys
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[[] for i in range(N)]
for k in range(N-1):#距離、点
    graph[A[k][2]].append([abs(A[k][0]-A[k-1][0]),A[k-1][2]])
    graph[A[k][2]].append([abs(A[k][0]-A[k+1][0]),A[k+1][2]])
graph[A[N-1][2]].append([abs(A[N-1][0]-A[N-2][0]),A[N-2][2]])
for k in range(N-1):
    graph[B[k][2]].append([abs(B[k][1]-B[k-1][1]),B[k-1][2]])
    graph[B[k][2]].append([abs(B[k][1]-B[k+1][1]),B[k+1][2]])
graph[B[N-1][2]].append([abs(B[N-1][1]-B[N-2][1]),B[N-2][2]])
#プリム法
kei = []
visit=[False]*N
heappush(kei,[0,0])#距離,点
dist = 0
point =0
while kei:
    d,i = heappop(kei)
    if point ==N:
        print(dist)
        sys.exit()
    if visit[i]==True:
        continue
    visit[i]=True
    dist += d
    point+=1
    for e,j in graph[i]:
        if not visit[j]:
            heappush(kei,[e,j])



### FIXED CODE ###

from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):#距離、点
    graph.append([min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]])
for k in range(N):
    graph.append([min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]])

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
#クラスカル法
kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0 = list(map(lambda x:x[1], ab0))
abn = list(map(lambda x:x[0], abn))


res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break
 
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n,q = map(int,raw_input().split())
Ai = 2**31-1
A = [Ai for i in range(n)]
for i in range(q):
    com,xi,yi = map(int,raw_input().split())
    if com==0: # update(xi,yi) 
        A[xi] = yi
    elif com==1:# find(xi,yi)
        print min(A[xi:yi+1])

### FIXED CODE ###

# coding: utf-8

n, q = map(int,raw_input().split())
A = [(1<<31) - 1 for i in xrange(100000)]
B = [(1<<31) - 1 for i in xrange(101)]
 
def update(i,x):
    if A[i] == (1<<31) - 1:
        A[i] = x
        B[i/1000] = min(x, B[i/1000])
    else:
        A[i] = x
        MIN = (1<<31) - 1
        for j in xrange(i/1000 * 1000, (i/1000 + 1) * 1000):
            if A[j] < MIN:
                MIN = A[j]
        B[i/1000] = MIN
 
def find(s,t):
    MIN = (1<<31) - 1
    if s/1000 == t/1000 or s/1000 + 1 == t/1000:
        for i in xrange(s, t+1):
            if A[i] < MIN:
                MIN = A[i]
    else:
        #left range
        for i in xrange(s, (s/1000 + 1) * 1000):
            if A[i] < MIN:
                MIN = A[i]
        #middle range
        for j in xrange(s/1000 + 1, t/1000):
            if B[j] < MIN:
                MIN = B[j]
         
        #right range
        for i in xrange(t/1000 * 1000, t+1):
            if A[i] < MIN:
                MIN = A[i]
    print MIN   
     
for i in xrange(q):
    com, s, t = map(int,raw_input().split())
    if com: #find
        find(s,t)
    else: #update
        update(s,t)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
ans,b,q=0,[],deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
while q:
  x,y=q.popleft()
  for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
    newx,newy=x+i,y+j
    if 0<=newx<h and 0<=newy<w:
      if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
        visited[newx][newy]=visited[x][y]+1
        q.append([newx,newy])
for i in range(h):
  for i in range(w):
    ans=max(ans,visited[i][j])
print(ans)

### FIXED CODE ###

from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans=0
n=int(input())
for i in range(n):
  for j in range(n):
    for k in range(n):
      ans+=gcd(i+1, j+1, k+1)
print(ans)

### FIXED CODE ###

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

import copy
import itertools
S = input()

K = 0
S__ = []
flag = False
prev = -1
for i in range(len(S)):
    S_ = list(itertools.combinations(range(len(S) - 1), i))
    for j in S_:
        if len(j) == 0:
            continue
        else:
            index = 0
            S__ = []
            buff = ""
            for k in range(len(S)):
                buff += S[k]
                if index >= len(j):
                    buff += S[k+1:]
                    S__.append(buff)
                    break
                if k == j[index]:
                    S__.append(buff)
                    buff = ""
                    index += 1
                    continue
            for k in range(len(S__) - 1):
                if S__[k] == S__[k + 1]:
                    break
                elif k == len(S__) - 2:
                    K = len(S__)
                    flag = True
            if flag:
                flag = False
                break
    if K == prev:
        print(K)
        exit(0)
    else:
        prev = K
    




    


### FIXED CODE ###

S = input()
ans = []

prev = ""
now = ""
for i in range(len(S)):
    now = now + S[i]
    if now != prev:
        ans.append(now)
        prev = now
        now = ""


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

# coding=utf-8
from functools import lru_cache

line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

@lru_cache()
def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = 0
    while l!=r:
        ret += calc(l,l+d)
        l += d
    print(ret)


### FIXED CODE ###

# coding=utf-8
line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

acc = [0 for _ in range(h*w+1)]
for dd in range(1,d+1):
    s = dd+d
    while s<=h*w:
        acc[s] = calc(s-d,s)+acc[s-d]
        s += d

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = acc[r] - acc[l]
    print(ret)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)

ans[0]=1
ans[1]=1
for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])


next=[1]
count = 1
while len(next)!=0:
    imaheya = next.pop(0)
    for i in range(len(ikeruheya[imaheya-1])):
        if ans[ikeruheya[imaheya-1][i]]==0:
            ans[ikeruheya[imaheya-1][i]]= imaheya             
            next.append(ikeruheya[imaheya-1][i])
            #ikeruheya[[imaheya-1][i]-1].remove(imaheya)
        

print("Yes")
for i in range(2, n+1):
    print(ans[i])


    
    


### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])
### BUGGY CODE ###

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

from operator import mul
from functools import reduce
from collections import Counter

def cmb(n,r):
    if r > n:
        return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

dict = Counter(A)

dict_cmb = {}
for k, v in dict.items():
    dict_cmb[k] = (cmb(v, 2), cmb(v-1, 2))

for a in A:
    ans = 0
    for k, v in dict_cmb.items():
        if a != k:
            ans += v[0]
        else:
            ans += v[1]
    print(ans)

### FIXED CODE ###

from collections import Counter

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

A_cnt = Counter(A)

x = 0
for i in A_cnt.values():
    x += i * (i-1) // 2

for a in A:
    ans = x - (A_cnt[a] * (A_cnt[a]-1) // 2)
    ans += (A_cnt[a]-1) * (A_cnt[a]-2) // 2
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().split()))

def solve():
    n = I()
    edge = [[] for _ in range(n)]
    for v in range(1,n):
        u = I()-1
        edge[u].append(v)

    dp = [None]*n
    def dfs(s)->int:
        if edge[s] == []:
            dp[s] = 0
            return 0
        tmp = []
        for v in edge[s]:
            tmp.append(dfs(v))
        tmp.sort(reverse=True)
        dp[s]=max(1+i+x for i,x in enumerate(sorted(tmp,reverse=1)))
        return dp[s]
    print(dfs(0))

if __name__=='__main__':
    solve()



### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

s = input()
n = int(input())
l = [list(input().split()) for i in range(n)]

for i in range(n):
    if l[i][0] == '1':
        s = s[::-1]
    else:
        if l[i][1] == '1':
            s = l[i][2] + s
        else:
            s += l[i][2]
print(s)

### FIXED CODE ###

import copy
from collections import deque
s = deque(input())
sc = copy.deepcopy(s) 
sc.reverse()
n = int(input())
l = [list(input().split()) for i in range(n)]

for i in range(n):
    if l[i][0] == '1':
        save = s
        s = sc
        sc = save
    elif l[i][1] == '1':
        s.appendleft(l[i][2])
        sc.append(l[i][2])
        #s = l[i][2] + s
        #sc += l[i][2]
    else:
        s.append(l[i][2])
        sc.appendleft(l[i][2])
        #s += l[i][2]
        #sc = l[i][2] + sc

print(''.join(s))
### BUGGY CODE ###

s = list(input(""))
Q = int(input())
c = 0
for i in range(Q):
    t = input()
    if len(t) == 1:
        c += 1
    elif t[2] == "1":
        if c%2 == 0:
            s.insert(0,t[4])
        else:
            s.append(t[4])
    else:
        if c%2 == 0:
            s.append(t[4])
        else:
            s.insert(0,t[4])

if c%2 == 0:
    for i in s:
        print(i,end="")
else:
    for i in s[::-1]:
        print(i,end="")

### FIXED CODE ###

s = input("")
Q = int(input())
c = 0
before = []
after = []
for i in range(Q):
    t = input()
    if len(t) == 1:
        c += 1
    elif t[2] == "1":
        if c%2 == 0:
            before.append(t[4])
        else:
            after.append(t[4])
    else:
        if c%2 == 0:
            after.append(t[4])
        else:
            before.append(t[4])

if c%2 == 0:
    print("".join(before[::-1]),end="")
    print(s,end="")
    print("".join(after),end="")
else:
    print("".join(after[::-1]),end="")
    print(s[::-1],end="")
    print("".join(before),end="")
### BUGGY CODE ###

s=list(input())
q=int(input())

for i in range(1,q+1):
    q_i=input().split()
    if q_i==["1"]:
        s=s[::-1]
    else:
        if q_i[1]=="1":
            s=list(q_i[2])+s
        else:
            s=s+list(q_i[2])

s="".join(s)
print(s)
    



### FIXED CODE ###

from collections import deque

s=list(input())
s=deque(s)
q=int(input())

re=False
for i in range(1,q+1):
    q_i=input().split()
    if q_i[0]=="1":
        re= not re
    else:
        if q_i[1]=="1" and re==False:
            s.appendleft(q_i[2])
        elif q_i[1]=="2" and re==True:
            s.appendleft(q_i[2])
        else:
            s.append(q_i[2])

s=list(s)

if re==True:
    s=s[::-1]

s="".join(s)
print(s)
### BUGGY CODE ###

import numpy as np
n = input()
a = np.array([*map(int, input().split())])
q = int(input())
b = [[*map(int,input().split())] for _ in range(q)]
for i,j in b:
    a = np.where(a==i, j, a)
    print(sum(a))

### FIXED CODE ###

import collections
_ = input()
a = [*map(int, input().split())]
q = int(input())
s = sum(a)
b = [[*map(int,input().split())] for _ in range(q)]
c = collections.Counter(a)
for i,j in b:
    if j not in c:
        c[j] = 0
    if i not in c:
        c[i] = 0
    s += (j-i)*c[i]
    c[j]+=c[i]
    c[i] = 0
    print(s)
### BUGGY CODE ###

n = int(input())
box = list(map(int,input().split()))

while(1):
    s = min(box)
    num = box.index(s)

    for index,item in enumerate(box):
    
        if num != index:
        
            if item % s == 0:
                box.remove(item)
            else:
                box[index] = item % s

    if len(box) == 1:
        break

print(box[0],end='')

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
ans = a[0]

for i,item in enumerate(a):
    if i != 0:
        ans = gcd(ans,item)

print(ans,end='')
### BUGGY CODE ###


count = 0
n = int(input())
a = list(map(int, input().split()))

for i in range(0,n-1):
    for o in range(1,n):
        if(a[i] + a[o] == o - i):
            count += 1

print(count)

### FIXED CODE ###


from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
lInfo = defaultdict(int)
rInfo = defaultdict(int)
cnt = 0

for i in range(n):
    lInfo[a[i]+i] += 1
    rInfo[i-a[i]] += 1

for k in lInfo.keys():
    cnt += lInfo[k] * rInfo[k]
print(cnt)
### BUGGY CODE ###

A,B=map(int,input().split())
gcd_list=[]
so_list=[]
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def coprime(a,b):
    return gcd(a,b)==1
for num in range(1,gcd(A,B)+1):
    if A%num==0 and B%num==0:
        gcd_list.append(num)
num=len(gcd_list)
if num>4:
    gcd_list=gcd_list[:num//2]
for i in gcd_list:
    flag=0
    if len(so_list)==0:
        so_list.append(i)
    else:
        for num in so_list:
            if num==1:
                continue
            if coprime(i,num)==False:
                flag=1
                break
        if flag==0:
            so_list.append(i)
print(len(so_list))


### FIXED CODE ###

from math import gcd
A, B = map(int,input().split())
max_cmn_div = gcd(A, B)

# 約数列挙関数
def make_divisor(n):
    divisor = []
    for i in range(1, int(n**(1/2))+1):
        if n % i == 0:
            divisor.append(i)
            if i != n//i:
                divisor.append(n//i)
    return divisor

def check_prime(n):
    for i in range(2, int(n**(1/2))+1):
        if n % i == 0:
            return 0
    return 1

cmn_div = make_divisor(max_cmn_div)
ans = 0
for i in cmn_div:
    if check_prime(i):
        ans += 1
print(ans)