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

import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    x = 1
    ans = 0
    # for a in A:
    #     tmp = gcd(x, a)
    #     # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    #     x = (x * a) // tmp

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = 0
    A = np.array(A)
    # for a in A:
    #     b += x // a
    b = np.sum(x//A, axis=0)
    print(b%MOD)
main()


### FIXED CODE ###

import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()
### BUGGY CODE ###

import math
from functools import reduce
import itertools 

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

_sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            _sum +=gcd(a, b, c)

print(_sum)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

_sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            _sum +=gcd(a, b, c)

print(_sum)
### BUGGY CODE ###

def resolve():
    s = input()
    q = int(input())
    qall = []
    for _ in range(q):
        inp = input()
        if inp == "1":
            s = s[::-1]
        else:
            z = inp.split()
            a = int(z[0])
            b = int(z[1])
            c = z[2]
            if b == 1:
                s = s[::-1]
                s = s + c
                s = s[::-1]
            else:
                s = s + c
    print(s)
resolve()

### FIXED CODE ###

def resolve():
    from collections import deque
    s = deque(input())
    q = int(input())
    qlist = [input().split() for i in range(q)]
    flip = False
    for j in range(q):
        if qlist[j][0] == "1":
            flip = not flip
        elif qlist[j][1] == "1":
            if flip:
                s.append(qlist[j][2])
            else:
                s.appendleft(qlist[j][2])
        elif qlist[j][1] == "2":
            if flip:
                s.appendleft(qlist[j][2])
            else:
                s.append(qlist[j][2])
    if not flip:
        print("".join(s))
    else:
        s.reverse()
        print("".join(s))
resolve()
### BUGGY CODE ###

import numpy as np

N = int(input())
a = list(map(int, input().split()))
a = np.sort(a)
count = 0
idxes = np.arange(len(a))
while len(idxes):
    idx = idxes[0]
    idxes = np.delete(idxes, 0)
    var = a[idx]
    if len(np.where(a[idxes] == var)[0]) == 0:
        count += 1
    idxes = idxes[np.where(a[idxes] % var != 0)[0]]
print(count)

### FIXED CODE ###

from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    ret = 0
    exist_counts = [0] * U
    for x in a:
        if exist_counts[x]:
            exist_counts[x] = 2
            continue
        idx = x
        while idx < U:
            exist_counts[idx] += 1
            idx += x
    for x in a:
        ret += exist_counts[x] == 1
    print(ret)
main()
### BUGGY CODE ###


import collections
n,ais = int(raw_input()), map(int, raw_input().split())
cc = collections.Counter()
for ai in ais:
	if ai % 4 == 0: cc[0] += 1
	elif ai % 2 == 0: cc[1] += 1
	else: cc[2] += 1

q = collections.deque()
h = {0:[2,1,0], 1:[1,0], 2:[0]} 
while(n):
	if len(q) == 0:
		for u in range(3)[::-1]:
			if cc[u] > 0:
				q.append(u)
				cc[u]-=1
				n -=1
				break
		if len(q) == 0: break
	else:
		for u in h[q[-1]] + [-1]:
			if u == -1:
				break
			if cc[u]:
				q.append(u)
				cc[u]-=1
				n-=1
				break

print 'Yes' if n == 0 else 'No'

### FIXED CODE ###


n,ais = int(raw_input()), map(int, raw_input().split())
import collections
cc = collections.Counter()
for ai in ais:
	if ai % 4 == 0: cc[0] += 1
	elif ai % 2 == 0: cc[1] += 1
	else: cc[2] += 1

q = collections.deque()
while(n):
	if len(q) == 0:
		for u in range(3)[::-1]:
			if cc[u] > 0:
				q.append(u)
				cc[u]-=1
				n -=1
				break
		if len(q) == 0: break
	else:
		if q[-1] == 0:
			if cc[2]:
				q.append(2)
				cc[2]-=1
				n-=1
			elif cc[1]:
				q.append(1)
				cc[1]-=1
				n-=1
			elif cc[0]:
				q.append(0)
				cc[0]-=1
				n-=1
			else:
				break
		elif q[-1] == 2:
			if cc[0] == 0:
				break
			else:
				q.append(0)
				cc[0]-=1
				n-=1
		elif q[-1] == 1:
			if cc[1] > 0:
				q.append(1)
				cc[1]-=1
				n-=1
			else:
				break

print 'Yes' if n == 0 else 'No'
### BUGGY CODE ###

R, G, B, n = map(int, input().split())
cnt = 0
for r in range(n//R+1):
  for g in range((n-r*R)//G+1):
    b = (n-r*R-g*G)//B
    if r * R + g*G + b*B == n:
      cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, n = map(int, input().split())
cnt = 0
for r in range(n//R+1):
  for g in range((n-r*R)//G+1):
    b = (n-r*R-g*G)//B
    if r * R + g*G + b*B == n:
      cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

# ほとんどは全体のmax
m = max(a)

for i in range(n):
  if a[i] == m:
    print(max(a[:i]+a[i+1:]))
  else:
    print(m)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

# ほとんどは全体のmax?
m1 = max(a)

# max値が多い場合用に2nd max
m2 = sorted(a)[n-2]

for i in range(n):
  if a[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = []
e = []
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            hw[h][w] = 0
            b.append([h, w])
        else:
            hw[h][w] = 1001
            e.append([h, w])

ans = 0
for ey, ex in e:
    ta = 2**31
    for by, bx in b:
        d = abs(ey-by)+abs(ex-bx)
        if d < ta:
            ta = d
    if ta > ans:
        ans = ta
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = deque()
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            b.append([h, w, 0])

ans = 0
while len(b) > 0:
    h, w, d = b.popleft()
    d += 1
    for y, x in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = h + y, w + x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == '.':
            b.append([nh, nw, d])
            if ans < d:
                ans = d
            hw[nh][nw] = "#"
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 8)

MAXN = 1005
MAXV = (MAXN * (MAXN - 1)) // 2
to = [[] for _ in range(MAXV)]
ID = [[-1] * MAXN for _ in range(MAXN)]

def toID(i, j):
    if i > j:
        i, j = j, i
    return ID[i][j]

visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV
def dfs(v): #DAGの最長経路を求める
    if visited[v]: #すでに訪れたことがある時
        if not calculated[v]: #計算されたことがない時 = ループがある
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res + 1)
    calculated[v] = True
    return dp[v]

def main():
    N = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    V = 0 #頂点の数
    for i in range(N - 1):
        for j in range(i + 1, N):
            ID[i][j] = V
            V += 1
    
    for i in range(N):
        for j in range(N - 1):
            a[i][j] = toID(i, a[i][j]) #対戦相手で管理していたのを試合番号に変える
        for j in range(N - 2):
            to[a[i][j + 1]].append(a[i][j])
    
    # import numpy as np
    # print (np.array(to))
    # print (np.array(ID))

    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print (-1)
            return 0
        ans = max(ans, res)
    print (ans)
    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

H,W=map(int,input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)

white=[]
black=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            cnt=0
            if (i+1)<H:
                if A[i+1][j]=="#":
                    cnt+=1
            if (i-1)>=0:
                if A[i-1][j]=="#":
                    cnt+=1
            if (j+1)<W:
                if A[i][j+1]=="#":
                    cnt+=1
            if (j-1)>=0:
                if A[i][j-1]=="#":
                    cnt+=1
            if cnt==4:
                pass
            else:
                black.append([i,j])
        else:
            white.append([i,j])
ans=0
for h,w in white:
    val=10**10
    for i,j in black:
        val1=abs(h-i)+abs(w-j)
        val=min(val,val1)
    ans=max(ans,val)

print(ans)

### FIXED CODE ###

from collections import deque
import sys
H,W=map(int,input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)
#多点スタートな最短路問題
q=deque()
dist=[[-1 for _ in range(W)]for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            dist[i][j]=0
            q.append([i,j])

dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)):
    h,w=q.popleft()
    #print(h,w)
    #print(q)
    for i in range(4):
        y=h+dy[i]
        x=w+dx[i]
        if (y<0)or(y>=H)or(x<0)or(x>=W):
            continue
        if dist[y][x]==-1:
            dist[y][x]=dist[h][w]+1
            q.append([y,x])
ans=0
#print(dist)
for i in range(len(dist)):
    ans=max(ans,max(dist[i]))
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(N)] 
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i, (w, v) in enumerate(x, 1):
    dpi = dp[i]
    dpim = dp[i-1]    
    for j in range(1, W + 1):
        if w <= j:
            a = dpim[j - w] + v
            if a > dpim[j]:
                dpi[j] = a
            else:
                dpi[j] = dpim[j]
        else:
            dpi[j] = dpim[j]

print(dp[-1][W])

### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

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

def green_bin(n,s):
    count = 0
    x = []
    for i in range(n):
        tmp = sorted(s[i])
        x.append(tmp)

    for i in range(n-1):
        si = x[i]
        for j in range(i+1,n):
            if i == j:
                continue
            else:
                sj = x[j]
                if si == sj:
                    count += 1

    return count
if __name__ == '__main__':
    n = int(input())
    s = [ input() for i in range(n)]

    print(green_bin(n,s))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
d = {}
ans = 0
for i in range(n):
    si = ''.join(sorted(raw_input()))
    if si in d:
        ans += d[si]
        d[si] += 1
    else:
        d[si] = 1
print(ans)
### BUGGY CODE ###

X,K,D=map(int,input().split())
i=0
count=0
if X<0:
	if X+K*D<=0:
		print(abs(X+K*D))
		count+=1
	else:
		L=X+i*D
		while L<=0:
			i+=1
			L=X+i*D
		if abs(L)>=abs(X+(i+1)*D):
			i+=1
			L=abs(X+i*D)
else:
	if X-K*D>=0:
		print(abs(X-K*D))
		count+=1
	else:
		L=X-i*D
		while L>=0:
			i+=1
			L=X-i*D
		if abs(L)>=abs(X-(i-1)*D):
			i-=1
			L=abs(X-i*D)
if count==0:
	kaisuu=K-i
	if kaisuu%2==0:
		print(abs(L))

	else:
		a=abs(L+D)
		b=abs(L-D)
		if a<=b:
			print(a)
		else:
			print(b)

		

### FIXED CODE ###

X,K,D=map(int,input().split())
X=abs(X)
count=0

if X-K*D>=0:
	print(X-K*D)
else:
	s=int(X/D)
	kaisuu=K-s
	if kaisuu%2==0:
		print(abs(X-s*D))
	else:
		print(abs(X-(s+1)*D))
### BUGGY CODE ###

from numpy.linalg import solve

N = int(input())
A = list(map(int, input().split()))
mat = [[0]*N for _ in range(N)]
A = [2*n for n in A]

for i in range(N):
    mat[i][i] = 1
    mat[i][(i+1)%N] = 1

ans = list(map(int, solve(mat, A)))
print(' '.join(map(str, ans)))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [-1]*N
ans[0] = sum(A[::2])-sum(A[1::2])

for i in range(1, N):
    ans[i] = 2*A[i-1] - ans[i-1]

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
h=np.array(input().split(),np.int64)
dp=np.zeros(n+1,np.int64)
# dp[i]:足場iに到達するための最小コスト。はじめカエルは足場1にいるのでdp[1]=0
dp[1]=0
dp[2]=abs(h[0]-h[1])
for i in range(3,n+1):      
      dp[i]=np.min([dp[i-j]+abs(h[i-1]-h[i-j-1]) for j in range(1,min(k+1,i))])
print(dp[n])

### FIXED CODE ###

n,k=map(int,input().split())
import numpy as np
h=np.array(input().split(),np.int64)
if n<3:
  print(abs(h[0]-h[1]))
  exit()
dp=np.zeros(n)
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
  j=max(0,i-k)
  dp[i]=np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
  #dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(k+1,i+1))])
print(int(dp[-1]))
### BUGGY CODE ###

n,m=map(int,input().split())
c = []
d = []
for i in range(m): 
  r = list(map(int,input().split()))
  if r[0] == 1 or r[1] == n:
    c.append(r)
    if r[1] == n:
      d.append(r[0])
ans = [z for z in c if z[0] == 1 and z[1] in d ]
print('IMPOSSIBLE' if len(ans) == 0 else 'POSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
lst = set()
fst = set()
for i in range(m): 
  r = list(map(int,input().split()))
  if r[1] == n:
    lst.add(r[0])
  elif r[0] == 1:
    fst.add(r[1])
print('IMPOSSIBLE' if len(fst & lst) == 0 else 'POSSIBLE')
### BUGGY CODE ###

N = int(input())
S = input()

left = 0
right = 1
max_length = 0

while left < N:
    serch_str = S[left:right]
    left_str = S[right:]
    if serch_str in left_str:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
        right = left + 1

print(max_length)



### FIXED CODE ###

N = int(input())
S = input()

left = 0
right = 1
max_length = 0

while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    if serch_str in S[right:]:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1

print(max_length)
### BUGGY CODE ###


import fractions as ft
#import math as ft


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // ft.gcd(a, lcm_)
#    print(lcm_)
    
ans = 0
for a in an:
    ans += lcm_ // a
    ans = ans % prime if ans >= prime else ans

print(ans)

### FIXED CODE ###


import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y), an ,0 )

print(ans%prime)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

n, z, w = map(int, input().split())
a = list(map(int, input().split()))

cache = {}

def f(idx, turn, x, y):
    if idx == n:
        return abs(x - y)
    
    key = (idx, turn)
    if key in cache:
        return cache[key]

    if turn == 0:
        ans = -float('inf')
        for i in range(idx, n):
            ans = max(ans, f(i + 1, 1 - turn, a[i], y))
    else:
        ans = float('inf')
        for i in range(idx, n):
            ans = min(ans, f(i + 1, 1 - turn, x, a[i]))

    cache[key] = ans
    return cache[key]

print(f(0, 0, z, w))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

n, z, w = map(int, input().split())
a = list(map(int, input().split()))

cache = {}

def f(idx, turn, x, y):
    if idx == n:
        return abs(x - y)
    
    key = (idx, turn)
    if key in cache:
        return cache[key]

    if turn == 0:
        ans = -float('inf')
        for i in range(idx, n):
            ans = max(ans, f(i + 1, 1 - turn, a[i], y))
    else:
        ans = float('inf')
        for i in range(idx, n):
            ans = min(ans, f(i + 1, 1 - turn, x, a[i]))

    cache[key] = ans
    return cache[key]

print(f(0, 0, z, w))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
max_x=max(A)+2
min_x=min(A)-1
l=[]
for x in range(min_x,max_x):
    cnt=0
    for a in A:
        if abs(x-a)<=1:
            cnt+=1
    l.append(cnt)
print(max(l))    

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[0]*(max(A)+3)
for a in A:
    ans[a-1]+=1
    ans[a]+=1
    ans[a+1]+=1
print(max(ans))
### BUGGY CODE ###

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

if M%N==0:
  print(M//N)
else:
  a=M//N
  while a>0:
    if (M-a*N)%a==0:
      print(a)
      break
    else:
      a-=1

### FIXED CODE ###

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

if M%N==0:
  print(M//N)
else:
  a=M//N
  while a>0:
    if (M-a*N)%a==0:
      print(a)
      break
    else:
      a-=1
### BUGGY CODE ###

n=int(input())
f=lambda:map(int,input().split())
a,b=f()
for _ in range(1,n):
  s,t=f(); x=y=0
  while x<a or y<b: x+=s; y+=t
  a,b=x,y
print(a+b)

### FIXED CODE ###

n=int(input())
f=lambda:map(int,input().split())
a,b=f()
for _ in range(1,n):
  c,d=f()
  t=max(1,0--a//c,0--b//d)
  a,b=c*t,d*t
print(a+b)
### BUGGY CODE ###

from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 0

    def bfs(x,y,G):
        prepare = 1 if A[y][x] == '#' else 0
        q = deque([(x, y, prepare)])
        MOVE = [(1,0), (0,1)]
        while q:
            z = q.popleft()
            
            for (a, b) in MOVE:
                w, h, c = z
                w_n, h_n = w+a, h+b

                if w_n >= W or h_n >= H:
                    continue
                if A[h_n][w_n] == '#':
                    c += 1
                
                d[h_n][w_n] = min(d[h_n][w_n], c)
                q.append((w_n, h_n, c))

    bfs(0, 0, A)
    return d[H-1][W-1]

print(solve())

### FIXED CODE ###

from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '#' else 0

    prepare = 1 if A[0][0] == '#' else 0
    q = deque([(prepare, 0, 0)])
    while q:
        c, x, y = q.popleft()
        for a, b in [(1,0), (0,1)]:
            nx, ny = x+a, y+b
            if nx >= W or ny >= H: continue
            k = 1 if A[y][x] != A[ny][nx] else 0
            if c+k >= d[ny][nx]: continue
            d[ny][nx] = c+k
            q.append((c+k, nx, ny))

    return (d[H-1][W-1]+1)//2

print(solve())
### BUGGY CODE ###

N=int(input())
S=input()

cnt = 0
z = 0
if N == 1:
    print("0")
    exit()
else:
    for i in range(N-1):
        x = S[i]
        y = S[i+1]
        if x == "#":
            if y == ".":
                cnt += 1
                S = S[0:i+1] + "#" + S[i+2:N]
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()

if N==1:
    print("0")
else:
    cnt_left=0
    cnt_right=S.count(".")
    cnt = cnt_left + cnt_right
    for i in range(N):
        if S[i] == "#":
            cnt_left += 1
        else:
            cnt_right -= 1

        if cnt_left + cnt_right < cnt:
            cnt = cnt_left + cnt_right
    print(cnt)
### BUGGY CODE ###

import math
def is_prime(n):
    if n == 1: return False
    # 2以外の偶数は素数ではないので無視する
    if n != 2:
        if n % 2 == 0:
            return False
    # 3以外の偶数は素数ではないので無視する
    if n != 3:
        if n % 3 == 0:
            return False
    # 5以外の偶数は素数ではないので無視する
    if n != 5:
        if n % 5 == 0:
            return False
    # 7以外の偶数は素数ではないので無視する
    if n != 7:
        if n % 7 == 0:
            return False
    # 11以外の偶数は素数ではないので無視する
    if n != 11:
        if n % 11 == 0:
            return False
            
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

a, b = map(int, input().split())
count = 1
for i in range(2,min(a,b)+1):
    if a % i == 0 and b % i == 0:
        if is_prime(i) == True:
            count += 1

print(count)


### FIXED CODE ###

# 再帰関数の最大回数を増やす
import sys
sys.setrecursionlimit(1000000)

import math

def gcd(i, j):
    """
    2値 i, j の最大公約数を求める。
    """

    if j == 0:
        return i
    else:
        return gcd(j, i % j)

def factorize(n):
    """
    素因数分解した個数を返す
    """
    count = 1
    rep = math.ceil(math.sqrt(n))
    for i in range(2, rep + 1):
        if n % i != 0:
            continue
        else:
            count += 1
            while n % i == 0:
                n /= i
        if n == 1:
            return count
    if n != 1:
        count += 1
    return count

def main():
    a, b = map(int, input().split())

    #最大公約数を求める
    x = gcd(a, b)

    #最大公約数を素因数分解する
    count = factorize(x)

    #結果を出力する
    print(count)

main()
### BUGGY CODE ###

n = int(input())
dic = {}
for i in range(n):
  num = input()
  if num not in dic.keys():
    dic[num] = 1
  elif dic[num] == 0:
    dic[num] = 1
  else:
    dic[num] = 0
print(sum(dic.values()))

### FIXED CODE ###

n = int(input())
A = [0] * n
for i in range(n):
  A[i] = int(input())
from collections import Counter
C = Counter(A)
counter = 0
for val in C.values():
  counter += val % 2
print(counter)
### BUGGY CODE ###

from sys import stdin, stdout
from time import perf_counter

import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7

# import sys
# sys.stdout = open("e:/python/cp/output.txt","w")
# sys.stdin = open("e:/python/cp/input.txt","r")



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

count =0
for i in range(a,b+1):
    if i%c==0:
        count+=1
print(count)



### FIXED CODE ###

from sys import stdin, stdout
from time import perf_counter

import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7

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

# y = ((b/x) -((a-1)/x))
print(((b//x) -((a-1)//x)))
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
arr=[[arr[i],i] for i in range(n)]
arr=sorted(arr,reverse=True,key=lambda x:x[0])
dp=[[-1]*(n+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(n):
    if dp[i][j]==-1:
      continue
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+arr[i][0]*abs(arr[i][1]-j))
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+arr[i][0]*abs(n-1-(i-j)-arr[i][1]))
print(max(dp[-1]))

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
arr=[[arr[i],i] for i in range(n)]
arr=sorted(arr,reverse=True,key=lambda x:x[0])
dp=[[-1]*(n+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(n):
    if dp[i][j]==-1:
      continue
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+arr[i][0]*abs(arr[i][1]-j))
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+arr[i][0]*abs(n-1-(i-j)-arr[i][1]))
print(max(dp[-1]))