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

# def gcd(a_gcd, b_gcd):
#     while b_gcd != 0:
#         a_gcd, b_gcd = b_gcd, a_gcd % b_gcd
#     return a_gcd
#
#
# def lcm(a_lcm, b_lcm):
#     return a_lcm * b // gcd(a_lcm, b_lcm)
#
#
# def max_sum(N_max_sum, a_max_sum):
#     dp = [0] * (N_max_sum + 1)
#     for i in range(N_max_sum):
#         dp[i + 1] = max(dp[i], dp[i] + a_max_sum[i])
#     return dp[N]
#
#
# def knapsack(N_knapsack, W, weight, value):
#     inf = float("inf")
#     dp = [[-inf for _ in range(W+1)] for j in range(N_knapsack + 1)]
#     for i in range(W+1):
#         dp[0][i] = 0
#
#     for i in range(N_knapsack):
#         for w in range(W+1):
#             if weight[i] <= w:
#                 dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
#             else:
#                 dp[i+1][w] = dp[i][w]
#     return dp[N_knapsack][W]


# # s = input()
# # N = int(input())
# N, K = map(int, input().split())
# # b = list(map(int, input().split()))
# # c = [list(map(int, input().split())) for _ in range(N)]
#
#
#
# print(N-K+1)

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

if B > R:
    B, R = R, B
if B > G:
    B, G = G, B

for r_i in range(N + 1):
    if r_i * R > N:
        break
    for g_i in range(N + 1):
        if r_i * R + g_i * G > N:
            break
        if (N - (r_i * R + g_i * G)) % B == 0:
            ans += 1

print(ans)

















### FIXED CODE ###

def gcd(a_gcd, b_gcd):
    while b_gcd != 0:
        a_gcd, b_gcd = b_gcd, a_gcd % b_gcd
    return a_gcd


def lcm(a_lcm, b_lcm):
    return a_lcm * b // gcd(a_lcm, b_lcm)


def max_sum(N_max_sum, a_max_sum):
    dp = [0] * (N_max_sum + 1)
    for i in range(N_max_sum):
        dp[i + 1] = max(dp[i], dp[i] + a_max_sum[i])
    return dp[N]


def knapsack(N_knapsack, W, weight, value):
    inf = float("inf")
    dp = [[-inf for _ in range(W+1)] for j in range(N_knapsack + 1)]
    for i in range(W+1):
        dp[0][i] = 0

    for i in range(N_knapsack):
        for w in range(W+1):
            if weight[i] <= w:
                dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    return dp[N_knapsack][W]


# # s = input()
# # N = int(input())
# N, K = map(int, input().split())
# # b = list(map(int, input().split()))
# # c = [list(map(int, input().split())) for _ in range(N)]
#
#
#
# print(N-K+1)

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

for r_i in range(N + 1):
    if r_i * R > N:
        break
    for g_i in range(N + 1):
        if r_i * R + g_i * G > N:
            break
        if (N - (r_i * R + g_i * G)) % B == 0:
            ans += 1

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

N = int(input())
A = list(map(int,input().split()))
ans = 0
L = []
for i in range(N) :
    for j in range(i+1,N+1) :
        L.append(sum(A[i:j]))
print(L.count(0))



### FIXED CODE ###

from math import factorial
N = int(input())
A = list(map(int,input().split()))
L = []
D = {}
ans = 0
L.append(0)
for i in range(len(A)) :
    L.append(L[-1]+A[i])
for j in range(len(L)) :
    if L[j] not in D :
        D[L[j]] = 1
    else :
        D[L[j]] += 1
V = list(D.values())
for k in range(len(V)) :
    if V[k] >= 2 :
        c = factorial(V[k])//(factorial(2)*factorial(V[k]-2))
        ans += c
print(ans)
### BUGGY CODE ###

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

def func(a,b):
    for i in range(21):
        if (a>>i)&(b>>i): #AND回路
            return False
    return True

def add_point(length):
    res = 0
    for i in range(1,length):
        res += i
    return res

ans = 0
i = 0
j = 1
flag = 0 #連続フラグ
while i < n:
    host = lst1[i]
    while j < n:
        if not func(host,lst1[j]):
            break
        host = host^lst1[j]
        j += 1
        ans += 1
    i += 1
    j = i+1
    

ans += n

print(ans)

### FIXED CODE ###

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

def func(a,b):
    for i in range(21):
        if (a>>i)&(b>>i): #AND回路
            return False
    return True

def add_point(length):
    res = 0
    for i in range(1,length):
        res += i
    return res

a,b,count,ans = 0,1,0,0
host = lst1[0]
#尺取法
while True:
    if b >= n and a >= n:
        break
    while  b<n and func(host,lst1[b]):
        host = host^lst1[b]
        b += 1
    host = host^lst1[a] #使わなくなる部分を引く
    if b -a > 1:
        ans += b-a-1
    a += 1

ans += n
print(ans)
### BUGGY CODE ###

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

S=0

for i in range(N):
    for k in range(N-i-1):
        S+=A[i]*A[i+k+1]

ans=S%1000000007

print(ans)


### FIXED CODE ###

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

mod=1000000007
S=0
sl=0

for i in range (N):
    sl+=A[i]
    sl%=mod
    
for j in range(N):
    sl-=A[j]
    if sl<0:
        sl+=mod
    S+=A[j]*sl
    S=S%mod

print(S)
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
h = list(map(int, input().split()))

d = [[float("inf")]*n for i in range(n)] 

for i in range(m):
    a, b = map(int, input().split())
    if (h[a-1] <= h[b-1]):
        d[a-1][b-1] = h[b-1]-h[a-1]
        d[b-1][a-1] = h[a-1]-h[b-1]
    else:
        d[a-1][b-1] = h[b-1]-h[a-1]
        d[b-1][a-1] = h[a-1]-h[b-1]
ans = 0 
for i in range(n):
    al = np.array(d[i])
    al = np.where(al==float('inf'), -1, al)
    if(len(np.where((al >= 0))[0]) == 0):
        ans += 1
print(ans)

### FIXED CODE ###

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

d = [True for i in range(n)] 

for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] > h[b-1]:
        d[b-1] = False
    elif h[a-1] < h[b-1]:
        d[a-1] = False
    elif h[a-1] == h[b-1]:
        d[a-1] = False
        d[b-1] = False

print(d.count(True))
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    while ts < 2500:
        ts += ccc[v]
        tt += ddd[v]
        if (ts, v) not in visited:
            heappush(q, (tt, ts, v))

print('\n'.join(map(str, ans[1:])))


### FIXED CODE ###

import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print('\n'.join(map(str, ans[1:])))
### BUGGY CODE ###

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

an = m //n
while an*n != m:
  an = m//n
  n = 1 + (m-1)*an
  
print(an)


### FIXED CODE ###

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

an = m //n
while an*n != m:
  an = m//n
  n = 1 + (m-1)//an
  
print(an)
### BUGGY CODE ###

S = input()

count = 0
while S.find("01") != -1 or S.find("10") != -1:
    if S.find("01") != -1:
        S = S.replace("01","",1)
    elif S.find("10") != -1:
        S = S.replace("10","",1)
    count += 2
print(count)

### FIXED CODE ###

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

K, S = map(int, input().split())
ans = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= S-i-j <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
x = 1
mod = 10**18
for i in range(n):
    x *= l[i]
if x > mod:
    print(-1)
    exit()
print(x)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
x = 1
mod = 10**18
if 0 in l:
    print(0)
    exit()
for i in range(n):
    x *= l[i]
    if x > mod:
        print(-1)
        exit()
print(x)
### BUGGY CODE ###

from collections import deque
from pprint import pprint
import sys
import copy
sys.setrecursionlimit(10**7)
def MI(): return map(int, sys.stdin.readline().split())


def bfs(q, sy, sx, ty, tx):
    visited[sy][sx] = 1
    while len(q) != 0:
        y, x, street, ans = q.popleft()
        # print(street)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            route = copy.copy(street)
            if 0 <= ny <= h-1 and 0 <= nx <= w-1 and visited[ny][nx] == 0:
                require[ny][nx] = require[y][x] + 1
                visited[ny][nx] = 1
                route.append([ny, nx])
                q.append([ny, nx, route, ans+direction[i]])
                if ny == ty and nx == tx:  # 探索終了
                    # pprint(require)
                    # pprint(visited)
                    # pprint(route)
                    y, x, route, ans = q.pop()
                    # pprint(ans)
                    return [route,ans]


sx, sy, tx, ty = MI()
sx += 1000
sy += 1000
tx += 1000
ty += 1000
h = 3000
w = 3000
maze = [[0] * w for _ in range(h)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
direction = ['L', 'U', 'R', 'D']


visited = [[0] * w for _ in range(h)]
require = [[0] * w for _ in range(h)]
que = deque()
que.append([sy, sx, [], ''])
route, ans = bfs(que, sy, sx, ty, tx)
# print(route)
# print(ans)


visited = [[0] * w for _ in range(h)]
require = [[0] * w for _ in range(h)]
for y, x in route:
    visited[y][x] = 1
visited[sy][sx] = visited[ty][tx] = 0

que.clear()
que.append([ty, tx, route, ans])
route, ans = bfs(que, ty, tx, sy, sx)
# print(route)
# print(ans)


visited = [[0] * w for _ in range(h)]
require = [[0] * w for _ in range(h)]
for y, x in route:
    visited[y][x] = 1
visited[sy][sx] = 0
visited[ty][tx] = 0

# pprint(visited)
que.clear()
que.append([sy, sx, route, ans])
route, ans = bfs(que, sy, sx, ty, tx)
# print(route)
# print(ans)


visited = [[0] * w for _ in range(h)]
require = [[0] * w for _ in range(h)]
for y, x in route:
    visited[y][x] = 1
visited[sy][sx] = 0
visited[ty][tx] = 0

que.clear()
que.append([ty, tx, route, ans])
route, ans = bfs(que, ty, tx, sy, sx)
# print(route)
print(ans)


visited = [[0] * w for _ in range(h)]
require = [[0] * w for _ in range(h)]
for y, x in route:
    visited[y][x] = 1
visited[sy][sx] = 0
visited[ty][tx] = 0
# pprint(visited)


### FIXED CODE ###

import sys
def MI(): return map(int, sys.stdin.readline().split())
sx, sy, tx, ty = MI()
dx = tx - sx
dy = ty - sy
print('U'*dy+'R'*dx+'D'*dy+'L'*dx+'L'+'U'*(dy+1)+'R'*(dx+1)+'DR'+'D'*(dy+1)+'L'*(dx+1)+'U')
### BUGGY CODE ###

import sys
h, w = [int(x) for x in input().split()]
mat = [input() for _ in range(h)]
cnt = [[0] * w for _ in range(h)]
row_obs = [[-1] for _ in range(h)]
col_obs = [[-1] for _ in range(w)]

def main():
    for i, r in enumerate(mat):
        for j, c in enumerate(r):
            if c == '#':
                row_obs[i].append(j)
                col_obs[j].append(i)
        row_obs[i].append(w)
    for j in range(w):
        col_obs[j].append(h)

    for i in range(h):
        k = 0
        while True:
            prev, nxt = (row_obs[i][k], row_obs[i][k+1])
            for j in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == w:
                break
            k += 1

    for j in range(w):
        k = 0
        while True:
            prev, nxt = (col_obs[j][k], col_obs[j][k+1])
            for i in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == h:
                break
            k += 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, cnt[i][j] - 1)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
h, w = [int(x) for x in input().split()]
mat = [input() for _ in range(h)]
cnt = [[0] * w for _ in range(h)]
row_obs = [[-1] for _ in range(h)]
col_obs = [[-1] for _ in range(w)]

def main():
    for i, r in enumerate(mat):
        for j, c in enumerate(r):
            if c == '#':
                row_obs[i].append(j)
                col_obs[j].append(i)
        row_obs[i].append(w)
    for j in range(w):
        col_obs[j].append(h)

    for i in range(h):
        k = 0
        while True:
            prev, nxt = (row_obs[i][k], row_obs[i][k+1])
            for j in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == w:
                break
            k += 1

    for j in range(w):
        k = 0
        while True:
            prev, nxt = (col_obs[j][k], col_obs[j][k+1])
            for i in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == h:
                break
            k += 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, cnt[i][j] - 1)
    print(ans)

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

class SegmentTree():
    def __init__(self,n):
        self.e = 0
        self.r = 0 #ノードの段数
        cnt = 0
        while cnt<n:
            cnt=2**self.r
            self.r +=1
        self.tree = [self.e]*(2**self.r -1)# 0-index
        self.n = 2**(self.r-1) #一番下のnodeの数
    def func(self,a,b): #適宜書き換え
        return a|b
    def update(self,i,val):
        i += self.n -1
        self.tree[i] = val
        while i>0:
            i = (i-1)//2
            self.tree[i] = self.func(self.tree[i*2+1],self.tree[i*2+2])

    def query(self,l,r):
        l += self.n -1
        r += self.n -1 #開区間 idxはr-1
        lval = self.e
        rval = self.e
        while r>l:
            if l%2 == 0:
                lval = self.func(lval,self.tree[l])
                l+=1
            if r%2==0:
                rval = self.func(rval,self.tree[r-1])
                r-=1
            r//=2
            l//=2
        return self.func(lval,rval)
    def index(self,i):
        return i+self.n -1
def sid(s):
    return ord(s)-ord("a") #chr("a") == 0

import sys
input = sys.stdin.readline
n = int(input())
S = input()[:-1]
Q = int(input())
seg = SegmentTree(n)
for i in range(n):
    s = S[i]
    seg.update(i,2**(sid(s)))
for q in range(Q):
    num,a,b = input().split()
    if num=="1":
        seg.update(int(a)-1,2**sid(b))
        #print(a,b,list(map(lambda x:bin(x)[2:],seg.tree)))
    else:
        print(bin(seg.query(int(a)-1,int(b))).count("1"))


### FIXED CODE ###

class SegmentTree():
    def __init__(self,n):
        self.e = 0
        self.r = 0 #ノードの段数
        cnt = 0
        while cnt<n:
            cnt=2**self.r
            self.r +=1
        self.tree = [self.e]*(2**self.r -1)# 0-index
        self.n = 2**(self.r-1) #一番下のnodeの数
    def func(self,a,b): #適宜書き換え
        return a|b
    def update(self,i,val):
        i += self.n -1
        self.tree[i] = val
        while i>0:
            i = (i-1)//2
            self.tree[i] = self.func(self.tree[i*2+1],self.tree[i*2+2])

    def query(self,l,r):
        l += self.n -1
        r += self.n -1 #開区間 idxはr-1
        lval = self.e
        rval = self.e
        while r>l:
            if l%2 == 0:
                lval = self.func(lval,self.tree[l])
                l+=1
            if r%2==0:
                rval = self.func(rval,self.tree[r-1])
                r-=1
            r//=2
            l//=2
        return self.func(lval,rval)
    def index(self,i):
        return i+self.n -1
def sid(s):
    return ord(s)-ord("a") #chr("a") == 0

import sys
input = sys.stdin.readline
n = int(input())
S = input()[:-1]
Q = int(input())
seg = SegmentTree(n)
for i in range(n):
    s = S[i]
    seg.update(i,2**(sid(s)))
for q in range(Q):
    num,a,b = input().split()
    if num=="1":
        seg.update(int(a)-1,2**sid(b))
        #print(a,b,list(map(lambda x:bin(x)[2:],seg.tree)))
    else:
        print(bin(seg.query(int(a)-1,int(b))).count("1"))
### BUGGY CODE ###

import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
position = [[]for i in range(n)]
for i in range(n):
    a, b= MAP()
    position[i] = (a, b)

def prim():
    res = 0
    used = [False]*n
    que = []
    heapq.heapify(que)
    used[0] = True
    for i in range(1, n):
        distance = min(abs(position[0][0]-position[i][0]), abs(position[0][1]-position[i][1]))
        heapq.heappush(que,(distance,i))
    while(len(que) > 0):
        cost, vertex = heapq.heappop(que)
        if used[vertex]:continue
        res += cost
        used[vertex] = True
        for i in range(n):
            if used[i]:continue
            distance = min(abs(position[vertex][0]-position[i][0]), abs(position[vertex][1]-position[i][1]))
            heapq.heappush(que,(distance, i))
    return res

print(prim())

### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
G = [[]for i in range(n)]   
position = [[]for i in range(n)]
for i in range(n):
    a, b= MAP()
    position[i] = (i, a, b)
position_x = sorted(position, key = lambda x:x[1])
position_y = sorted(position, key = lambda x:x[2])

for i in range(1,n):
    G[position_x[i][0]].append((position_x[i][1]-position_x[i-1][1], position_x[i-1][0]))
    G[position_x[i-1][0]].append((position_x[i][1]-position_x[i-1][1], position_x[i][0]))
    G[position_y[i][0]].append((position_y[i][2]-position_y[i-1][2], position_y[i-1][0]))
    G[position_y[i-1][0]].append((position_y[i][2]-position_y[i-1][2], position_y[i][0]))

def prim(G):
    res = 0
    used = [False]*n
    que = []
    heapq.heapify(que)
    used[0] = True
    for Gs in G[0]:
        heapq.heappush(que,Gs)
    while(len(que) > 0):
        cost, vertex = heapq.heappop(que)
        if used[vertex]:continue
        res += cost
        used[vertex] = True
        for Gs in G[vertex]:
            if used[Gs[1]]:continue
            heapq.heappush(que,Gs)
    return res

print(prim(G))
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = 0
mod = int(1e9+7)
import fractions
# def gcd(a,b):
#   while b != 0:
#     a, b = b, a % b
#   return a
# 最小公倍数
def lcm(a,b):
    return (a*b) // fractions.gcd(a,b)

g = 1
for i in range(n):
    g = lcm(g, s[i])
for i in range(n):
    ans += g // s[i] % mod
print(ans%mod)



### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = 0
mod = int(1e9+7)
def gcd(a,b):
  while b != 0:
    a, b = b, a % b
  return a
def lcm(a,b):
    return a // gcd(a,b) * b

g = 1
for i in range(n):
    g = lcm(g, s[i])
for i in range(n):
    ans += g // s[i]
print(ans%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
asum=sum(a)
y=[0]*(n+1)
for i in range(asum+1):
    y[0]=i
    flag=True
    for j in range(1,n+1):
        y[j]=(a[j-1]-y[j-1]//2)*2
        if y[j]<0:
            flag=False
            break
    if flag:
        if y[0]==y[n]:
            y.pop(n)
            print(*y)
            exit()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
asum=sum(a)
y=[0]*n
y[-1]=a[-1]
for i in range(n-1):
    if i%2==0:
        y[-1]-=a[i]
    else:
        y[-1]+=a[i]
for i in range(n-1):
    y[i]=a[i-1]*2-y[i-1]
print(*y)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import math
from fractions import gcd

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

# 最大公約数
g = gcd(A, B)

if g == 1:
    print(1)
    exit()

ggg = set()
for i in range(1, g+1):
    if A%i == 0 and B%i == 0:
        ggg.add(i)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime = get_sieve_of_eratosthenes(g)
#print(prime)

print( len(ggg & set(prime)) +1 )

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

from fractions import gcd

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

# 最大公約数
g = gcd(A, B)

if g == 1:
    print(1)
    exit()

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

print(len(prime_factorize(g)) +1)