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

import math
n=int(input())
a=list(map(int,input().split()))
soin = [0]*(10**6+1)
if a.count(1)==n:
    print("pairwise coprime")
    exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return arr


if len(a)>80000:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        if i ==1:continue
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n and 1 not in a:
        print("not coprime")
    else:print("setwise coprime")


### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
soin = [0]*(10**6+1)
if a.count(1)==n:
    print("pairwise coprime")
    exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return arr


if len(a)>80000:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        if i ==1:continue
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n and 1 not in a:
        print("not coprime")
    else:print("setwise coprime")
### BUGGY CODE ###

def main():
    K, S = map(int, input().split())
    cnt = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if x + y + z == S:
                    cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    K, S = map(int, input().split())
    cnt = 0
    for x in range(K+1):
        for y in range(K+1):
            z = S - x - y
            if 0 <= z and z <= K:
                cnt += 1
    print(cnt)


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

S=input()
dp=[]
for _ in range(len(S)):
    dp.append([0]*13)
if S[0]=='?':
    for i in range(10):
        dp[0][(i*10**(len(S)-1))%13]=1
else:
    dp[0][(int(S[0])*10**(len(S)-1))%13]=1
for j in range(0,len(S)-1):
    for k in range(13):
        if S[j+1]=='?':
            L=[]
            for l in range(10):
                l=(l*10**(len(S)-j-2)%13)
                L.append(dp[j][k-l])
            dp[j+1][k]+=sum(L)%(7+10**9)
        else:
            dp[j+1][k]=dp[j][k-(int(S[j+1]))*10**(len(S)-j-2)%13]
print((dp[len(S)-1][5])%(7+10**9))


### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

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

res = 0
bits = [[0]*2 for _ in range(60)]
for a in al:
    for i in range(60):
        bits[i][int(bin(a >> i)[-1])] += 1

res = 0

for i in range(60):
    res += bits[i][0] * bits[i][1]  * (2 ** i) % (10 ** 9 + 7)

print(res % (10 ** 9 + 7))

### FIXED CODE ###


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

res = 0
bits = [0]*60
for a in al:
    i = 0
    b = a
    while b:
        bits[i] += b&1
        b = b >> 1
        i += 1

res = 0

for j in range(60):
    res += bits[j] * (n - bits[j])  * (2 ** j)

print(res % (10 ** 9 + 7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, m, s, t = map(int, input().split())
G1 = [[]for i in range(n+1)]
G2 = [[]for i in range(n+1)]
cost1 = [10**15 ]*(n+1)
cost2 = [10**15 ]*(n+1)
for i in range(m):
    u, v, a, b = map(int,input().split())
    G1[u] += (v,a),
    G1[v] += (u,a),
    G2[u] += (v,b),
    G2[v] += (u,b),
def f1(s, l, c):
    if cost1[s] > c:
        cost1[s] = c
    for v, a in G1[s]:
        if v not in l:
            f1(v, l+[v], c+a)
def f2(t, l, c):
    if cost2[t] > c:
        cost2[t] = c
    for v, b in G2[t]:
        if v not in l:
            f2(v, l+[v], c+b)
f1(s, [s], 0)
f2(t, [t], 0)
ansl = []
ans = 0
for i in range(1, n+1):
    cost = cost1[-i] + cost2[-i]
    m = 10**15 - cost
    if ans < m:
        ans = m
    ansl.append(ans)
for _ in range(n):
    print(ansl.pop())
    

### FIXED CODE ###

from heapq import heappop, heappush
 
 
def dijkstra(costs, s, i):
    q = [(0, s)]
    while q:
        c, v = heappop(q)
        if costs[v] >= 0:
            continue
        costs[v] = c
        for link in links[v]:
            u = link[0]
            if costs[u] == -1:
                heappush(q, (c + link[i], u))
 
 
n, m, s, t = map(int, input().split())
links = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    links[u] += (v, a, b),
    links[v] += (u, a, b),

yen_costs = [-1] * (n+1)
snk_costs = [-1] * (n+1)
dijkstra(yen_costs, s, 1)
dijkstra(snk_costs, t, 2)
ansl = []
ans = 0

for i in range(1, n+1):
    cost = yen_costs[-i]+snk_costs[-i]
    m = 10**15 - cost
    if ans < m:
        ans = m
    ansl.append(ans)
for _ in range(n):
    print(ansl.pop())
### BUGGY CODE ###


A = input()
a = int(A)
ans  = 0 
for i in range(len(A)):
    for j in range(i+4,len(A)+1):
        t = A[i:j]
        ans += (int(t)%2019==0)
print(ans)

### FIXED CODE ###

s=list(map(int,list(input())))[::-1]

n=len(s)
D=[0]*(n+1)
c=[0]*(n+1)
ans = 0
f = 0
dp = [0]*(2020)
dp[0]+=1
tmp =0
x = 1
for e,i in enumerate(s):
    tmp = (tmp+x*i)%2019
    ans += dp[tmp]
    dp[tmp]+=1
    x = x*10 %2019
print(ans)
### BUGGY CODE ###

from collections import deque
li = deque()
n = int(input())

for i in range(n):
	command = input().split()
	if command[0] == 'insert':
		li.append(command[1])
	if command[0] == 'find':
		if command[1] in li:
			print('yes')
		else:
			print('no')

### FIXED CODE ###

from collections import defaultdict

d = defaultdict(lambda: 0)

N = int(input())

for _ in range(N):
    ord, str = input().split()
    if ord == 'insert':
        d[str] = 1
    else:
        if str in d:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

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

l.sort(reverse = 1)
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        indL = j
        indR = len(l)-1
        while indL <= indR:
            #print(i,indL,indR)
            if l[i] < l[indL] + l[indR]:
                ans += (indR - indL)
                break
            else:
                indR -= 1
            
print(ans)

### FIXED CODE ###

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

l.sort(reverse = 1)
ans = 0

for i in range(n-2):
    indL = i+1
    indR = len(l)-1
    while 1:
        if indL == indR:
            break
        if l[i] < l[indL] + l[indR]:
            ans += (indR - indL)
            indL += 1
        else:
            indR -= 1
                
print(ans)
### BUGGY CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
ans = 0
teams = []
for i in range(N):
    teams.append([l[0],l[1],l[-1]])
    l.remove(l[0])
    l.remove(l[1])
    l.remove(l[-1])

print(sum([i[1] for i in teams]))

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
ans = l[1::2]

print(sum(ans[:N]))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
    B, C = map(int, input().split())
    A += [C]*B
A.sort(reverse = True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
D = []
sum_B=0
for B, C in BC:
    D += [C] * B
    sum_B += B
    if sum_B>N:
        break

A+=D
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
#lr = [list(map(int,input().split()))for _ in range(Q)]
#l = [lr[i][0] for i in range(Q)]
#r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * (N+2)
cnt = 0

for i in range(1,N+1):
    #if S[i]+S[i+1]=='AC':
        #c[i+1]+=1
    c[i] = S[:i].count('AC')

#print(c)

for i in range(Q):
    #print(sum(c[:j])-sum(c[:i]))
    l,r = map(int,input().split())
    print(c[r]-c[l])

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * N
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
    #c[i] = S[:i].count('AC')

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    #l,r = map(int,input().split())
    print(c[j-1]-c[i-1])
### BUGGY CODE ###

n = int(input())
S = input()
R,G,B = [],[],[]
ans = 0

for i in range(len(S)):
  if S[i] == 'R':
    R.append(i+1)
  elif S[i] == 'G':
    G.append(i+1)
  else:
    B.append(i+1)

for r in R:
  for g in G:
    for b in B:
      a,b,c = sorted([r,g,b])
      if b-a != c-b:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
cnt = 0

for i in range(n):
  for j in range(i+1,n):
	# j-i == k-j <=> k == 2j-i
    k = 2*j-i
    if k >= n or k <= j:
      break
    if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
      cnt += 1
print(r*g*b - cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
if m%n==0:
    print(m//n)
elif n > m//2:
    index = m
    while index >0:
        if m%index==0:
            if m//index > n-1:
                print(index)
                break
        index+=1
else:
    index=1
    while index <m+1:
        if m%index==0:
            if index > n-1:
                print(m//index)
                break
        index+=1


### FIXED CODE ###

import math
import time
n, m = map(int, input().split())
flag=0
if m%n==0:
    print(m//n)

else:
    start = time.time()
    index=m//n
    while index >0:
        elapsedTime = time.time()-start
        if elapsedTime > 1:
            flag=1
            break
        elif m%index==0:
            print(index)
            break
        index-=1

    if flag==1:
        index = 1
        while index < m+1:
            if m % index == 0:
                if index > n-1:
                    print(m//index)
                    break
            index += 1
### BUGGY CODE ###

H, W, K = map(int, input().split())
HW = [list(map(int, list(input()))) for _ in range(H)]

def blocks(hw):
    score = 0
    blank = -1
    flg = True
    delcnt = 0
    while flg:
        flg = False
        for h in range(H):
            cnt = 1
            old = hw[h][:]
            for w in range(1, W):
                if hw[h][w-1]==hw[h][w]:
                    cnt+=1
                    flg = True
                else:
                    if cnt>=K:
                        score += 2**delcnt*cnt*hw[h][w-1]
                        for k in range(1, cnt+1):
                            hw[h][w-k] = blank
                            blank -= 1
                    cnt = 1
            if cnt>=K:
                score += 2**delcnt*cnt*hw[h][W-1]
                for k in range(1, cnt+1):
                    hw[h][W-k] = blank
                    blank -= 1
        for w in range(W):
            cnt = 1
            for h in range(H-1, -1, -1):
                item = hw[h][w]
                hw[h][w] = blank
                blank -= 1
                if item>0:
                    hw[H-cnt][w] = item
                    cnt += 1
        delcnt += 1
    return score
import copy
ans = []
if K>=4:
    print(0)
else:
    for h in range(1, H):
        for w in range(W):
            hw = copy.deepcopy(HW)
            for i in range(H-h, 0, -1):
                hw[i][w] = hw[i-1][w]
            hw[0][w] = 0
            ans.append(blocks(hw))
print(max(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
H, W, K = map(int, input().split())
HW = [list(map(int, list(str(input().strip())))) for _ in range(H)]

def blocks(hw):
    score = 0
    ret = 1
    delcnt = 0
    while ret:
        ret = check(delcnt, hw)
        score += ret
        delcnt += 1
    return score

def check(delcnt, hw):
    s = 0
    blank = -1
    for h in range(H):
        cnt = 1
        old = hw[h][:]
        for w in range(1, W):
            if hw[h][w-1]==hw[h][w]:
                cnt+=1
                flg = True
            else:
                if cnt>=K:
                    s += cnt*hw[h][w-1]
                    for k in range(1, cnt+1):
                        hw[h][w-k] = blank
                        blank -= 1
                cnt = 1
        if cnt>=K:
            s += cnt*hw[h][W-1]
            for k in range(1, cnt+1):
                hw[h][W-k] = blank
                blank -= 1
    for w in range(W):
        cnt = 1
        for h in range(H-1, -1, -1):
            item = hw[h][w]
            hw[h][w] = blank
            blank -= 1
            if item>0:
                hw[H-cnt][w] = item
                cnt += 1
    return 2**delcnt*s

import copy
ans = []
if K>=4:
    print(0)
else:
    for h in range(1, H):
        for w in range(W):
            hw = copy.deepcopy(HW)
            for i in range(H-h, 0, -1):
                hw[i][w] = hw[i-1][w]
            hw[0][w] = 0
            ans.append(blocks(hw))
print(max(ans))
### BUGGY CODE ###



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

h = list(map(int, input().split()))

dp = [1000000000] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], (dp[i] + abs(h[i] - h[i+j])))

print(dp[n-1])

### FIXED CODE ###

import sys

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

h = list(map(int, input().split()))

dp = [1000000000] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], (dp[i] + abs(h[i] - h[i + j])))

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

import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d = [min(d[0],d1[i]+d2[i])] + d
[print(10**15-c) for c in d]

### FIXED CODE ###

import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]
### BUGGY CODE ###

a, b, x = map(int,input().split())
tmp = a
while True:
    if tmp % x == 0:
        break
    else:
        tmp += 1
li = [i for i in range(tmp,b+1,x)]
print(len(li))


### FIXED CODE ###

a, b, x = map(int,input().split())
print((b//x)-(a-1)//x)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    XYR = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(n):
        x, y, r = map(int, input().split())
        XYR.append([x, y, r])

    cost = [[0] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        x1, y1, r1 = XYR[i]
        for j in range(n + 2):
            x2, y2, r2 = XYR[j]
            dist = max(0, pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5) - (r1 + r2))
            cost[i][j] = cost[j][i] = dist

    def dijkstra(s):
        # 始点sから各頂点への最短距離
        # n:頂点数, cost[u][v]:辺uvのコスト(存在しないときはinf)
        d = [f_inf] * (n + 2)
        used = [False] * (n + 2)
        d[s] = 0

        while True:
            v = -1
            # まだ使われてない頂点の中から最小の距離のものを探す
            for k in range(n + 2):
                if (not used[k]) and (v == -1):
                    v = k
                elif (not used[k]) and d[k] < d[v]:
                    v = k
            if v == -1:
                break
            used[v] = True

            for m in range(n + 2):
                d[m] = min(d[m], d[v] + cost[v][m])
        return d

    res = dijkstra(0)
    print(res[1])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    XYR = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(n):
        x, y, r = map(int, input().split())
        XYR.append([x, y, r])

    cost = [[0] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        x1, y1, r1 = XYR[i]
        for j in range(n + 2):
            x2, y2, r2 = XYR[j]
            dist = max(0, pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5) - (r1 + r2))
            cost[i][j] = cost[j][i] = dist

    def dijkstra(s):
        # 始点sから各頂点への最短距離
        # n:頂点数, cost[u][v]:辺uvのコスト(存在しないときはinf)
        d = [f_inf] * (n + 2)
        used = [False] * (n + 2)
        d[s] = 0

        while True:
            v = -1
            # まだ使われてない頂点の中から最小の距離のものを探す
            for k in range(n + 2):
                if (not used[k]) and (v == -1):
                    v = k
                elif (not used[k]) and d[k] < d[v]:
                    v = k
            if v == -1:
                break
            used[v] = True

            for m in range(n + 2):
                d[m] = min(d[m], d[v] + cost[v][m])
        return d

    res = dijkstra(0)
    print(res[1])


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

s = str(input())
q = int(input())
state = True
front = ""
ending = ""
for _ in range(q):
  qi = str(input())
  if qi[0] == "2":
    fi,ci = map(str,qi[2:].split())
    if state == True:
      if fi == "1":
        front += ci
      else:
        ending += ci
    else:
      if fi == "1":
        ending += ci
      else:
        front += ci
  else:
    state = not state
if state:
  first = front[::-1]
  lastt = ending
else:
  first = ending[::-1]
  lastt = front
  s = s[::-1]
print(first+s+lastt)

### FIXED CODE ###

s = str(input())
q = int(input())
state = True
front = ""
ending = ""
for _ in range(q):
  qi = str(input())
  if qi[0] == "2":
    fi,ci = map(str,qi[2:].split())
    if state == True:
      if fi == "1":
        front += ci
      else:
        ending += ci
    else:
      if fi == "1":
        ending += ci
      else:
        front += ci
  else:
    state = not state
if state:
  first = front[::-1]
  lastt = ending
else:
  first = ending[::-1]
  lastt = front
  s = s[::-1]
print(first+s+lastt)
### BUGGY CODE ###

total, tar = list(map(int, input().split()))
dice_array = list(map(int, input().split()))
l = [] * total

tar2 = 0
calc_before = 0
calc_now = 0
for i in range(total+1-tar):
  calc_now = sum(dice_array[i:i+tar])
  if calc_before < calc_now:
    tar2 = i
    calc_before = calc_now
  calc_now = 0

sum_data = 0
cnt = 0
for i in range(tar2, tar+tar2):
  cnt = sum(list(range(1, dice_array[i] + 1)))
  sum_data += (cnt / dice_array[i])
  
print(sum_data)


### FIXED CODE ###

total, tar = list(map(int, input().split()))
dice_array = list(map(int, input().split()))

hope_array = [0.0] * total
for i in range(total):
   hope_array[i] = (dice_array[i] * (dice_array[i] + 1)) / 2 / dice_array[i]

dice_total = [0]
 
for i in range(total):
  dice_total.append(hope_array[i] + dice_total[i])
 
ans = dice_total[tar]
tar_num = tar
for i in range(total - tar):
  tmp = dice_total[i + 1 + tar] - dice_total[i + 1]
  if ans < tmp:
    ans = tmp

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

import sys

_ = input()
S = input().strip()
idx = [i+1 for i in range(len(S)-1) if S[i:i+2] == 'AC']

for line in sys.stdin:
  l,r = list(map(int, line.strip().split(' ')))
  print(sum([1 for i in idx if l <= i <= r-1]))

### FIXED CODE ###

import sys
_ = input()
S = input().strip()

ps = [0]*(len(S)+1)
for i in range(2, len(S)+1):
  ps[i] = ps[i-1]+int(S[i-2:i] == 'AC')

for line in sys.stdin:
  l,r = map(int, line.strip().split(' '))
  print(ps[r]-ps[l])
### BUGGY CODE ###

def hoge(n):
 return n.isdigit();

raw_input()
a = map(int,raw_input().split(" "))
raw_input()
b = map(int,filter(hoge,raw_input().split(" ")))

result = 0
for i in b:
    if i in a:
        result += 1

print result

### FIXED CODE ###

def hoge(n):
    return n.isdigit();

raw_input()
a = map(int,filter(hoge,raw_input().split(" ")))
a.sort()
raw_input()
b = map(int,filter(hoge,raw_input().split(" ")))

result = 0
for i in b:
    for j in a:
        if i < j:
            break
        if i == j:
            result += 1
            break

print result
### BUGGY CODE ###

import sys
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

A, B = map(int, input().split())
gcd_AB = gcd(A, B)
if gcd_AB == 1:
  print(1)
  exit(0)
if gcd_AB == 2:
  print(2)
  exit(0)

so_list = []
for i in range(3, gcd_AB, 2):
  if A%i !=0 or B%i !=0:
    continue
  flag=True
  for s in so_list:
    if i%s == 0:
      flag=False
      break
  if flag:
    so_list.append(i)

if A%2 ==0 or B%2 ==0:
  so_list.insert(0,2)
#print(so_list)
print(len(so_list) + 1)


### FIXED CODE ###

import math
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

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, B = map(int, input().split())
gcd_AB = gcd(A, B)
# 素因数分解
p_list = prime_factorize(gcd_AB)
#print(p_list)
print(len(set(p_list))+1)