Harryxun/stf_run huggingface dataset:
# ABC067D - Fennec VS. Snuke (ARC078D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, x: int, y: int) -> None:
    D[y][v] = x
    for u in G[v]:
        if not D[y][u]:
            dfs(u, x + 1, y)


def main():
    global G, D
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    D = [[0] * (N + 1) for _ in range(2)]
    dfs(1, 1, 0), dfs(N, 1, 1)
    b, w = 0, 0
    for i, j in zip(*D[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC067D - Fennec VS. Snuke (ARC078D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

from collections import deque


def bfs(s, d) -> None:
    q = deque([s])
    while q:
        v = q.popleft()
        for u in G[v]:
            if not d[u]:
                q.append(u)
                d[u] = d[v] + 1


def main():
    global G, DB, DW
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    bfs(1, DB), bfs(N, DW)
    b, w = 0, 0
    for i, j in zip(DB[1:], DW[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()
s = input()
# print(s[2:len(s)])
l = len(s)
count = 0


# for i, j in itertools.combinations(range(len(s)+1), 2):
#     if(int(s[i:j]) % 2019 == 0):
#         count = count + 1
#
# print(count)

for i in range(2019):
    count2 = 0
    for j in range(l):
        if int(s[j:l]) % 2019 == i:
            count2 = count2 + 1
    count = count + (count2 * (count2 - 1)) / 2
print(int(count))

### FIXED CODE ###

s, w = map(int, input().split())
if s > w:
  print("safe")
else:
  print("unsafe")
x,y,z = map(input().split())

print(z,x,y)

### FIXED CODE ###

x,y,z = map(int,input().split())

print(z,x,y)
CV = 380000.0
N=int(input())
total = 0
for i in range(N):
  x,u = input().split()
  x = int(x)
  if u == "BTC":
    x *= CV
  total += x
print(total)

### FIXED CODE ###

CV = 380000.0
N=int(input())
total = 0
for i in range(N):
  x,u = input().split()
  x = float(x)
  if u == "BTC":
    x *= CV
  total += x
print(total)
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0:
        return 1
    elif i == 1:
        return 1
    else:
        if i in memo:
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2, memo)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2, memo)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1, memo)
print(num % 1000000007)


### FIXED CODE ###

N, M = map(int, input().split())
kaidan = [0] * (N + 1)
for i in range(M):
    tmp = int(input())
    kaidan[tmp] = -1
kaidan[0] = 1
for i in range(1,N + 1):
    if i == 1:
        if kaidan[i] != -1:
            kaidan[i] = 1
        else:
            kaidan[i] = 0
    else:
        if kaidan[i] != -1:
            kaidan[i] = kaidan[i -1] + kaidan[i - 2]
        else:
            kaidan[i] = 0
print(kaidan[N] % (10 ** 9 + 7))
def acwa():
x,y = map(int,input().split())
if x = y:
	print('Yes');
else x < y:
  	print('No');

### FIXED CODE ###

str1, str2 = [s for s in input().split()]
if str1 == str2:
    print('Yes')
else:
    print('No')
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if min(pos, DP[pos], DP[pos] + 1 - DP[i]) >= 0:
            DP[i], ans[i] = DP[pos] + 1, j

S, pos = "", N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = map(int, raw_input().split())

DP = [0] + [-1] * N
ans = [0] * N + [0]

for i in range(1, N + 1):
    for j in range(10)[::-1]:
        if not j in A:
            continue
        if cost[j] > i:
            continue
        if DP[i - cost[j]] < 0:
            continue
        if DP[i] < DP[i - cost[j]] + 1:
            DP[i] = DP[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = N
while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S
a=[]
for i in range(3):
    a.append(int(input()))
x=int(input())
ans+=1

for i in range(a[0]):
    for j in range(a[1]):
        for k in range(a[2]):
            if i*500+j*100+k*50==x:
                ans+=1
print(ans)

### FIXED CODE ###

a=[]
for i in range(3):
    a.append(int(input()))
x=int(input())
ans=0

for i in range(a[0]+1):
    for j in range(a[1]+1):
        for k in range(a[2]+1):
            if i*500+j*100+k*50==x:
                ans+=1
print(ans)
print (6.28*R)

### FIXED CODE ###

R = float(input())
print(R*6.28)
from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in range(n)]

    c=0
    while any(map(len,d)):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip.copy():
                #if d[i]:
                if d[i][0] in skip:
                    continue
                elif i==d[d[i][0]][0]:
                    oppo=d[i].popleft()
                    d[oppo].popleft()
                    skip.add(oppo)
                    skip.add(i)
                    f=1
                        
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print(-1)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

if __name__ == '__main__':
    main()
string = list(input())
times = int(input())
#a = [int(i) for i in range(0,5)]
#print(a)
for i in range(times):
    order = input().split()
    #print(order)
    if order[0] == "replace":
        replace_string = order[3]
        #print(string)
        count = 0
        for j in range(int(order[1]), int(order[2]) + 1):
            string[j] = replace_string[count]
            count += 1
            #print(count)
        #print(string)
    elif order[0] == "reverse":
        #print(string)
        reverse_string = string[int(order[1]):int(order[2]) + 1]
        reverse_string.reverse()
        for j in range(int(order[1]), int(order[2]) + 1):
            string[j] = reverse_string[j]
        #print(j)
        #print(string)
        #string[int(order[1]):int(order[2]) + 1].reverse()
        #print(string)
        #string[int(order[1]):int(order[2])] = string[int(order[1]):int(order[2])].reverse()
    elif order[0] == "print":
        #print(string)
        print("".join(string[int(order[1]):int(order[2]) + 1]))
        #print(string)

### FIXED CODE ###

string = list(input())
times = int(input())
for i in range(times):
    order = input().split()
    if order[0] == "replace":
        replace_string = order[3]
        count = 0
        for j in range(int(order[1]), int(order[2]) + 1):
            string[j] = replace_string[count]
            count += 1
    elif order[0] == "reverse":
        reverse_string = string[int(order[1]):int(order[2]) + 1]
        reverse_string.reverse()
        string = string[:int(order[1])] + reverse_string + string[int(order[2])+1:]
    elif order[0] == "print":
        print("".join(string[int(order[1]):int(order[2]) + 1]))
import math

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

g = math.gcd(a,b)


ans = 1
for i in range(2,g):
    while g%i == 0:
        g=g//i
        isdevided = True
    if isdevided:
        ans += 1
        isdevided = False

print(ans)


### FIXED CODE ###

import math
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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

g = gcd(a,b)


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

if temp!=1:
    arr.append([temp, 1])

print(len(arr)+1)
n, m = tuple(map(int, input().split()))
list = list(map(int, input().split()))
list = sorted(list)

diff = []
for i in range(len(list) - 1):
    diff.append(list[i] - list[i+1])

abs_diff = []
for i in range(len(diff)):
    abs_diff.append(abs(diff[i]))

abs_diff = sorted(abs_diff)

if abs_diff != []:
    for _ in range(n - 1):
        abs_diff.pop(abs_diff.index(max(abs_diff)))

print(sum(abs_diff))

### FIXED CODE ###

n, m = tuple(map(int, input().split()))
x = list(map(int, input().split()))
x = sorted(x)

diff = []

for i in range(len(x) - 1):
    diff.append(x[i + 1] - x[i])

diff = sorted(diff)

diff_sum = 0
diff_len = m - 1

for i in range(diff_len - (n - 1)):
    diff_sum += diff[i]

print(diff_sum)
N = int(input())

def get_parent(node):
    parent = -1
    if "parent" in node:
        parent = node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" not in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" in node:
        return "root"
    if "left" in node:
        return "leaf"
    return "internal node"

def get_children(node):
    if "left" not in node:
        return "[]"
    left = node["left"]
    siblings = []
    siblings.append(str(left))
    while rooted_tree[left]["right"] > -1:
        right = rooted_tree[left]["right"]
        siblings.append(str(right))
        left = right
    return "[{}]".format(", ".join(siblings))

rooted_tree = [{} for i in range(N)]
for id in range(N):
    row = input()
    _, degree, *children = list(map(int, row.split()))
    if degree > 0:
        rooted_tree[id]["left"] = children[0]
        for i in range(len(children)):
            child_id = children[i]
            right = -1
            if i < len(children)-1:
                right = children[i+1]
            rooted_tree[child_id]["right"] = right
            rooted_tree[child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    depth = get_depth(node)
    node_type = get_node_type(node)
    children = get_children(node)
    print("node {}: parent = {}, depth = {}, {}, {}".format(id, parent, depth, node_type, children))


### FIXED CODE ###

N = int(input())

def get_parent(node):
    parent = -1
    if "parent" in node:
        parent = node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" not in node:
        return "root"
    if "left" not in node:
        return "leaf"
    return "internal node"

def get_children(node):
    if "left" not in node:
        return "[]"
    left = node["left"]
    siblings = []
    siblings.append(str(left))
    while rooted_tree[left]["right"] > -1:
        right = rooted_tree[left]["right"]
        siblings.append(str(right))
        left = right
    return "[{}]".format(", ".join(siblings))

rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input()
    id, degree, *children = list(map(int, row.split()))
    if degree > 0:
        rooted_tree[id]["left"] = children[0]
        for i in range(len(children)):
            child_id = children[i]
            right = -1
            if i < len(children)-1:
                right = children[i+1]
            rooted_tree[child_id]["right"] = right
            rooted_tree[child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    depth = get_depth(node)
    node_type = get_node_type(node)
    children = get_children(node)
    print("node {}: parent = {}, depth = {}, {}, {}".format(id, parent, depth, node_type, children))
s = int(input())
w = int(input())
if w >= s:
    print("unsafe")
else:
    print("safe")

### FIXED CODE ###

s,w = map(int,input().split())
if w >= s:
    print("unsafe")
else:
    print("safe")
hoge = input()
huga = hoge ** 3 
print(huga)

### FIXED CODE ###

input_lines = int(input())
print(input_lines **3)
loop = input()
a = map(int, input().split())
cnt = 0
 
while(1):
  flg = 0
  for i in a:
    if(a%2 == 1):
      flg = 1
      
  if(flg == 0):
    a = map(lamda x:x/2, a)
    cnt += 1
  else:
    break
 
print(cnt)


### FIXED CODE ###

a = input()
cnt = 0
for i in a:
  if i == '1':
    cnt+=1
    
print(cnt)
num = int(input())

if num[-1] == 2 or 4 or 5 or 7 or 9:
  print("hon")
elif num[-1] == 0 or 1 or 6 or 8:
  print("pon")
else:
  print("bon")

### FIXED CODE ###

num = int(input()[-1])
 
if num == 3:
  print("bon")
elif num == 0 or num ==1 or num ==6 or num ==8:
  print("pon")
else:
  print("hon")
import numpy as np
X = int(input())
for b in range(np.ceil(np.sqrt(X))):
    p = 0
    while b**p <= X:
        p += 1
    p -= 1
    ans = max(ans, b**p)
print(ans)


### FIXED CODE ###

import numpy as np
X = int(input())
ans = 1
for b in range(2, 1+int(np.ceil(np.sqrt(X)))):
    p = 0
    while np.power(b, p) <= X:
        p += 1
    p -= 1
    ans = max(ans, np.power(b, p))
print(ans)
N = int(input())
S = int(input())
count == 0
for i in range(N):
    if S[i+1] != S[i]:
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
S = list(input())
#print(S)
count = 1
for i in range(N):
    if i == 0:
        continue
    elif S[i-1] != S[i]:
        count += 1

print(count)
n = int(input())
p_li = list(map(int,input().split()))
min_v = p_li[0]
ans=1
for x in p_li:
    if x == 1
    	ans+=1
        break
    if min_v>=x:
        min_v=x
    else:
        ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
p_li = list(map(int,input().split()))
min_v = p_li[0]
ans=1
for x in p_li:
    if min_v>x:
        min_v=x
        ans+=1
print(ans)
N, Y = map(int, input().split())

flag=0
for x in range(N+1):
	for y in range(N+1):
		z = N -(x + y)
		if 0<=z<=N and en_sum==Y:
			en_sum = 10000*x + 5000*y + 1000*z
			print(x, y, z)
			flag+=1
		break

if flag==0:
	print(-1, -1, -1)

### FIXED CODE ###

#入力
N, Y = map(int, input().split())


#総当たりで合計金額を算出
x = []
y = []
z = []

for num_ten_thousand in range(0, N+1):
    for num_five_thousand in range(0, N+1):
            
            #千円の枚数を算出
            if N-(num_ten_thousand+num_five_thousand)>=0:
                num_one_thousand = N-(num_ten_thousand+num_five_thousand)
            
            #合計金額を算出
            total = num_ten_thousand*10000 + num_five_thousand*5000 + num_one_thousand*1000
            
            #（合計金額がYと等しいか・合計枚数がNと等しいか）を確認し答えをリストに格納
            if Y==total and N==num_ten_thousand+num_five_thousand+num_one_thousand:
                x.append(num_ten_thousand)
                y.append(num_five_thousand)
                z.append(num_one_thousand)
                
                
#答えを出力
if not x:
    print(-1, -1, -1, sep=" ")
    
else:
    print(x[0], y[0], z[0], sep=" ")
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def union(self, a, b):
        self.parent[self.find(b)] = self.find(a)

n, m = map(int, input().split())
UF = UnionFind(n)
for _ in range(m):
    a,b = map(int, input().split())
    UF.union(a-1,b-1)
o=set()
for i in range(n):
    o.add(UF.fins(i))
print(len(o) - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def union(self, a, b):
        self.parent[self.find(b)] = self.find(a)

n, m = map(int, input().split())
UF = UnionFind(n)
for _ in range(m):
    a,b = map(int, input().split())
    UF.union(a-1,b-1)
o=set()
for i in range(n):
    o.add(UF.find(i))
print(len(o) - 1)
from collections import Counter
from functools import reduce
import copy
import bisect
import fractions
import math
import statistics
import sys
import time
from sympy import isprime
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # Greatest Common Divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # Least Common Multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


n = II()
# a = LI()
a = sorted(LI())
maxi = -INF
ans = 1

for i in range(n):
    if isprime(a[i]) == True:
        del a[i]
        print(GCD_LIST(a))
        exit()

while True:
    div = GCD_LIST(a)
    a = list(map(lambda x: x // div , a))
    if div == 1:
        for j in range(n):
            if isprime(a[j]) == True or 1 in a:
                    del a[j]
                    print(ans * GCD_LIST(a))
                    exit()
        del a[0]
        print(ans * GCD_LIST(a))
        exit()
        
    ans *= div

# test = [i for i in range(100000)]
# start = time.time()
# print(GCD_LIST(test))
# for i in range(n):
#     tmp = copy.copy(a) 
#     del tmp[i]
#     maxi = max(maxi,GCD_LIST(tmp))
# print(maxi)


#for i in range(len(test)):
#    tmp = copy.copy(test) 
#    del tmp[i]
#    maxi = max(maxi,GCD_LIST(tmp))
#    print(i)
#print(maxi)


### FIXED CODE ###

from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


n, a = II(), LI()
left = [0] * (n+1)
right = [0] * (n+1)

for i in range(1, n+1):
    left[i] = fractions.gcd(left[i-1], a[i-1])

for i in range(n-1, -1, -1):
    right[i] = fractions.gcd(right[i+1], a[i]) 

# print(left)
# print(right)

maxi = -INF

for i in range(n):
    maxi = max(maxi, fractions.gcd(left[i],right[i+1]))

print(maxi)
s = input()
if s[0] == "A":
  C = []
  for i in range(3, len(s)-2):
    if s[i] == "C":
      C.append(i)
  if len(C) != 1:
    print("WA")
    break 
  else:
    up = False
    for j in range(1,len(s)):
      if j == C[0]:
        pass
      elif s[j].isupper:
        up = True
    if up:
      print("WA")
    else:
      print("AC")
else:
  print("WA")
    

### FIXED CODE ###

s = list(input())
if s[0] == "A":
  C = []
  for i in range(2, len(s)-1):
    if s[i] == "C":
      C.append(i)
  if len(C) != 1:
    print("WA")
  else:
    up = False
    for j in range(1,len(s)):
      if j == C[0]:
        continue
      elif not s[j].islower():
        up = True
    if up:
      print("WA")
    else:
      print("AC")
else:
  print("WA")
ss = {i:list(input()) for i in "abc"}
x = ss[a].pop(0)
while True:
  if not ss[x]:
    print(x.upper())
    break
  else:
    x = ss[x][0]

### FIXED CODE ###

aa = input()
bb = input()
cc = input()
def kansu(char,a,b,c):    
    if char == 'a':
        if not a:
            return 'A'
        else:
            char = a[0:1]
            a = a[1:]
            r = kansu(char,a,b,c)
    elif char == 'b':
        if not b:
            return 'B'
        else:
            char = b[0:1]
            b = b[1:]
            r = kansu(char,a,b,c)
    else:
        if not c:
            return 'C'
        else:
            char = c[0:1]
            c =c[1:]
            r = kansu(char,a,b,c)
    return r
            
charc = aa[0:1]
aa = aa[1:]
result = kansu(charc,aa,bb,cc)
print(result)
from math import *
import sympy
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def eratosthenes(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
                
    return prime_list
a,b = map(int,input().split())
upper = int(sqrt(min(a,b))) + 1
pl = set(eratosthenes(upper))
common_factor = make_divisors(a)&make_divisors(b)
ans = 0
for i in common_factor:
    if i in pl:
        ans += 1
print(ans + 1)

### FIXED CODE ###

def factorize(n):
    fct = []
    b,e = 2,0
    while b*b <= n:
        while n % b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b,e))
        b,e = b+1,0
    if n > 1:
        fct.append((n,1))
    return fct
a,b = map(int,input().split())
ap = set()
for prime,count in factorize(a):
    ap.add(prime)
bp = set()
for prime,count in factorize(b):
    bp.add(prime)
print(len(ap&bp)+1)