Harryxun/stf_run huggingface dataset:
MOD = 1000000007

def solve(N, ABs):
    groups = {}
    for a, b in ABs:
        k = a / b
        groups.setdefault(k, 0)
        groups[k] += 1

    visited = set()
    possibles = []
    for k, v in groups.items():
        if k in visited:
            continue
        p = 0
        p += pow(2, v, MOD)
        m = - (1.0 / k)
        if m in groups.keys():
            p += pow(2, groups[m], MOD)
            visited.add(m)
            p -= 1
        possibles.append(p % MOD)

    ans = 1
    for p in possibles:
        ans *= p
        ans %= MOD
    return ans - 1


if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))


### FIXED CODE ###

import math
MOD = 1000000007

def solve(N, ABs):
    groups = {}
    zero_count = 0
    for a, b in ABs:
        if a == 0 and b == 0:
            zero_count += 1
            continue
        if a == 0:
            k = (0, 1)
        elif b == 0:
            k = (1, 0)
        else:
            g = math.gcd(abs(a), abs(b))
            a //= g
            b //= g
            if a * b < 0:
                k = (abs(a), -abs(b))
            else:
                k = (abs(a), abs(b))
        groups.setdefault(k, 0)
        groups[k] += 1

    visited = set()
    possibles = []
    for k, v in groups.items():
        if k in visited:
            continue
        p = 0
        p += pow(2, v, MOD)
        if k[1] == 0:
            m = (0, 1)
        elif k[0] == 0:
            m = (1, 0)
        else:
            if k[1] < 0:
                m = (-k[1], k[0])
            else:
                m = (k[1], -k[0])


        if m in groups.keys() and m not in visited:
            p += pow(2, groups[m], MOD)
            visited.add(m)
            p -= 1
        visited.add(k)
        possibles.append(p % MOD)

    ans = 1
    for p in possibles:
        ans *= p
        ans %= MOD

    if zero_count:
        ans += zero_count
        ans %= MOD
    return (ans - 1) % MOD


def slow_solve(N, ABs):
    import itertools
    ans = 0
    for k in range(1, 2**N):
        b = ("{:0" + str(N) + "b}").format(k)
        taken = []
        for i, c in enumerate(b):
            if c == "1":
                taken.append(ABs[i])

        if len(taken) == 1:
            ans += 1
        elif all(comb[0][0] * comb[1][0] + comb[0][1] * comb[1][1] != 0
                 for comb in itertools.combinations(taken, 2)):
            ans += 1
    return ans % MOD



if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))
import numpy as np
from numba import njit

@njit(cache=True)
def update(A, N):
    B = [0] * N
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if (r + 1 < N):
            B[r + 1] -= 1
    return np.cumsum(B)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(0, min(100, K)):
        A = update(A, N)
    print(" ".join([str(item) for item in A]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
n=input()
n_list=list(map(int,input().split()))

counter=0
while all(i%2==0 for i in n_list):
     n_list=[i/2 for i in n_list]

    #n_list=[i/2 for i in n_list]
    counter=+1
print(counter)

### FIXED CODE ###

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

while True:
   if [i for i in a if i % 2 == 1]:
       break
   a = [i/2 for i in a]
   cnt += 1

print(cnt)
n = int(input())
s = input()
l = 0
r = n - 1
ans = 0
while l < r:
    while l < r && s[l] == 'R':
        l += 1
    while l < r && s[r] == 'W':
        r -= 1
    ans += 1
    l += 1
    r -= 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
l = 0
r = n - 1
ans = 0

while l < r:
    while l < r and s[l] == 'R':
        l += 1
    while l < r and s[r] == 'W':
        r -= 1
    if l >= r:
        break
    ans += 1
    l += 1
    r -= 1

print(ans)
import math
input()
lc = 1
for i in range(n):
    t = int(input())
    lc = lc * t // math.gcd(lc,t)
print(lc)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = int(input())
lc = 1
for i in range(n):
    t = int(input())
    lc = lc * t // gcd(lc,t)
print(lc)
N = int(input())
a = [int(i) for i in input().split()]
S = 0
for i in range(N):
  if a[a[i]] == i:
    S += 1
print(S//2)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
S = 0
for i in range(N):
  if a[a[i]-1] == i+1:
    S += 1
print(S//2)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
N,M,X = map(int,input().split()) #整数の入力
a = list(map(int,input().split()))
#検問所の入力
b=[]
c=[]
for i in range(X+1,N): #X+1からNの範囲の整数について 
  if i in a: #ある整数が検問所の整数として存在する
    b.append(1)
for i in range(1,X): #1からX-1の範囲の整数について
  if i in a: #ある整数が検問所の整数として存在する
    c.append(1)
print(min(sum(b),sum(c))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
N,M,X = map(int,input().split()) #整数の入力
a = list(map(int,input().split()))
#検問所の入力
b=[]
c=[]
for i in range(X+1,N): #X+1からNの範囲の整数について 
  if i in a: #ある整数が検問所の整数として存在する
    b.append(1)
for i in range(1,X): #1からX-1の範囲の整数について
  if i in a: #ある整数が検問所の整数として存在する
    c.append(1)
print(min(sum(b),sum(c)))
N = int(input())
A = list(map(int, input().split()))


dp = [0] * 10
dp[0] = 1000
for i in range(1,N):
    dp[i] = dp[i-1]
    for j in range(0,i):
        V = int(dp[j] / A[j])
        W = dp[j] + (A[i] - A[j]) * V
        dp[i] = max(dp[i], W)
print(dp[N-1])





### FIXED CODE ###


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


dp = [0] * 100
dp[0] = 1000
for i in range(1,N):
    dp[i] = dp[i-1]
    for j in range(0,i):
        V = int(dp[j] / A[j])
        W = dp[j] + (A[i] - A[j]) * V
        dp[i] = max(dp[i], W)
print(dp[N-1])
a = input().split()

for i in range(0,2):
  if(a[i]=="7"):
    print("yes")
  elif(i==2 and a[2] != "7"):
    print("No")

### FIXED CODE ###

a = input()

if(a.count("7")!=0):
    print("Yes")
else:
    print("No")
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

AB.sort(key = lambda x:x[1],reverse=True)
ans =0
cnt = 0
i = 0
daylist = [i+1 for i in range(M)]
while i<N:
    d = AB[i][0]
    if d > M:continue
    if daylist[d] > 0 and cnt < M:
        daylist[d] = daylist[d]-1
        ans += AB[i][1]
        cnt += 1
    i += 1
print(ans)

### FIXED CODE ###


N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
import heapq
AB.sort()
heap = []
heapq.heapify(heap)
ans = 0
i = 0
day = 1
while day <= M:
    while i < N and AB[i][0] <= day:
        heapq.heappush(heap,-AB[i][1])
        i += 1
    day += 1
    if not(heap):continue
    ans -= heapq.heappop(heap)

print(ans)
a= input()
b=input()
if a==b:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

from sys import stdin
a, b = stdin.readline().rstrip().split()
if (a==b):
  print('Yes')
else:
  print('No')
import cmath
import math
n=int(input())
a=[]
b=[]
#偏角ソートの方が楽
for i in range(n):
    x,y=map(int,input().split())
    if (x,y)!=(0,0):
        a.append(complex(x,y))
        b.append(cmath.phase(a[i]))
    else:
        n-=1
#a.sort(key=cmath.phase)
m=0
#math.piに注意
for i in range(n):
    za,zb=0,0
    for j in range(n):
        p=cmath.phase(a[j]/a[i])
        if -math.pi<=p<=0:
            za+=a[j]
        if 0<=p<=math.pi:
            zb+=a[j]
    m=max([abs(za),abs(zb),abs(za-a[i]),abs(zb-a[i]),m])
print(m)


### FIXED CODE ###

import cmath
import math
n=int(input())
a=[]
b=[]
#偏角ソートの方が楽
for i in range(n):
    x,y=map(int,input().split())
    a.append(complex(x,y))
    b.append(cmath.phase(a[i]))
#a.sort(key=cmath.phase)
ma=0
#math.piに注意
for i in range(n):
    z=a[i]
    c=b[i]-math.pi/2
    d=b[i]+math.pi/2
    l=max([c,-math.pi])
    r=min([d,math.pi])
    #(0,0)の時は偏角が0になってしまうし、除く
    #あとは-piとpiどっちになるか→piになる
    if a[i]!=complex(0,0):
        for j in range(n):
            if j!=i:
                #境界条件の場合分けがむずい
                if l<=b[j]<=r or (c<=-math.pi and c+2*math.pi<=b[j]<=math.pi) or (d>=math.pi and -math.pi<=b[j]<=d-2*math.pi):
                    z+=a[j]
    ma=max([abs(z),ma])
m=0
#math.piに注意
for i in range(n):
    if a[i]!=complex(0,0):
        za,zb=complex(0,0),complex(0,0)
        for j in range(n):
            p=cmath.phase(a[j]/a[i])
            if -math.pi<=p<=0:
                za+=a[j]
            if 0<=p<=math.pi:
                zb+=a[j]
        m=max([m,abs(za),abs(zb)])
        if i!=n-1 and a[i]+a[i+1]!=0:
            zc,zd=complex(0,0),complex(0,0)
            for j in range(n):
                p=cmath.phase(a[j]/((a[i]+a[i+1])/2))
                if -math.pi<=p<=0:
                    zc+=a[j]
                if 0<=p<=math.pi:
                    zd+=a[j]
            m=max([m,abs(zc),abs(zd)])

print(max([m,ma]))
r= int(input())
p= 3.141592653589793238
print(p*r**2,2*p*r)

### FIXED CODE ###

from math import pi
r = float(input())
print(round(r * r * pi, 7), round(2 * pi * r, 7))
def nCr(n, r):
    import math
    return math.factorial(n) // ((math.factorial(n - r) * math.factorial(r)))
MOD = 1000000007

n, k = map(int, input().split())
b, r = k, n-k
for i in range(0, k):
    x = nCr(b - 1,  i) # 青いブロックの分け方
    y = nCr(r + 1 , r- i)

    print(x * y % MOD)

### FIXED CODE ###

s = input()
l = ""
res = True
for i in range(4):
    if s[i] == l:
        res = False
    l = s[i]
print("Good" if res else "Bad")
n = int(input())
li = list(map(int,input().split()))
prod = 1
for i in range(n):
	prod *= li[i]

count = 0
while (prod % (2**n)) == 0:
	prod = int(prod / (2**n))
	count += 1
print(count)

### FIXED CODE ###

input()
A = list(map(int, input().split()))
count = 0
while all(a % 2 == 0 for a in A):
    A = [a/2 for a in A]
    count += 1
print(count)
n=int(input())
A=[int(input()) for i in range(n)]
s=0

Z=[]
R=[]
z=0
r=0
for a in A:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)

for i in range(n-1,-1,-1):
  if Z[i]>=R[i]:
    s+=sum(A[:i+1])
    A=A[i+1:]
    
    break

if A==[]:
  print(s)
  exit()
  
Z=[]
R=[]
z=0
r=0
for a in A[::-1]:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)
Z=Z[::-1]
R=R[::-1]

for i in range(len(A)):
  if Z[i]>=R[i]:
    s+=sum(A[i:])
    A=A[:i]
    break

if A==[]:
  print(s)
  exit()

for i in range(len(A)):
  if A[i]==0:
    s+=1
    A[i]=1
s0=s

O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i] and f==1:
    s+=O[i]
    A=A[i+1:]

    break
  if A[i]==1:
    f=1
O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i]:
    s+=O[i]
    A=A[i+1:]

    break


O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i] and f==1:
    s0+=O[i]
    A=A[i+1:]

  if A[i]==1:
    f=1
O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i]:
    s0+=O[i]
    A=A[i+1:]

    break

print(min(s,s0)) 


### FIXED CODE ###

n=int(input())
zot=lambda x:0 if x==0 else (x+1)%2+1
A=[int(input()) for i in range(n)]
D=[0,0,0,0,0]

for a in A:
  d0 = D[0] + a
  d1 = min(D[:2])+ [2,1,0][zot(a)]
  d2 = min(D[:3])+ [1,0,1][zot(a)]
  d3 = min(D[:4])+ [2,1,0][zot(a)]
  d4 = min(D) + a
  D=[d0,d1,d2,d3,d4]
print(min(D))
N, K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
for l in range(K):
    for r in range(0 , K - l):
        if l + r > K:
            continue
        d = K - (r + l)
        now = 0
        hold = []
        for i in range(l):
            hold.append(V[i])
        for i in range(1 , r + 1):
            hold.append(V[-i])
        hold.sort()
        now = sum(hold)
        for i in range(d):
            if i >= len(hold):
                break
            if hold[i] > 0:
                break
            else:
                now -= hold[i]
        ans = max(ans , now)
print(ans)

### FIXED CODE ###

from collections import deque
from copy import deepcopy
N, K = map(int, input().split())
#V = list(map(int, input().split()))
V = deque(map(int, input().split()))
ans = 0
for l in range(K + 1):
    for r in range(0 , K - l + 1):
        work_V = deepcopy(V)
        if l + r > N:
            continue
        d = K - (r + l)
        now = 0
        hold = []
        for i in range(l):
            #hold.append(V[i])
            hold.append(work_V.popleft())
        for i in range(N - r , N):
            #hold.append(V[-i])
            hold.append(work_V.pop())
        hold.sort()
        now = sum(hold)
        for i in range(d):
            if i >= len(hold):
                break
            if hold[i] > 0:
                break
            else:
                now -= hold[i]
        ans = max(ans , now)
print(ans)
import sys

q = int(input())
for a in range(q):
    X = input()
    Y = input()
    cost = [0]
    for c in Y:
        for i in range(len(cost) - 1, -1, -1):
            index = X.find(c, cost[i]) + 1
            if index:
                if i + 1 < len(cost):
                    cost[i + 1] = min(cost[i + 1], index)
                else:
                    cost.append(index)
    print(len(cost) - 1)

### FIXED CODE ###

def solve():
    a1 = raw_input()
    a2 = raw_input()
    a = len(a1)
    b = len(a2)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = a1[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == a2[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i2 in range(n):
    print solve()
i = list(map(int, input().split()))
j = [int(0)] * 9

n=i[9]

#print(j)

for b in range(9):
    for c in range(n):
        if i[b]==i[10+c]:
            j.insert(b,1)

#print(j)     

if  j[0]==1 and j[3]==1 and j[6]==1\
or j[1]==1 and j[4]==1 and j[7]==1\
or j[2]==1 and j[5]==1 and j[8]==1\
or j[0]==1 and j[1]==1 and j[2]==1\
or j[3]==1 and j[4]==1 and j[5]==1\
or j[6]==1 and j[7]==1 and j[8]==1\
or j[0]==1 and j[4]==1 and j[8]==1\
or j[2]==1 and j[4]==1 and j[6]==1:
    print('yes')
else:
    print('no')

### FIXED CODE ###

#import numpy as np

i=[input().split() for l in range(4)]

n=int(i[3][0])

j = [input() for i in range(n)]

#i=np.array(i)
#print(i)


k = [['0' for o in range(3)] for p in range(3)]

for b in range(3):
    #print('b:',b)
    for c in range(3):
        #print('c:',c)
        for d in range(n):
            #print('d:',d)
            if i[b][c]==j[d]:
                k[b][c]='1'
                #print('書き換えたよ',k)
                
                
#print(i)
#print(j)
#print(k)


if  k[0][0]=='1' and k[0][1]=='1' and k[0][2]=='1'\
or k[1][0]=='1' and k[1][1]=='1' and k[1][2]=='1'\
or k[2][0]=='1' and k[2][1]=='1' and k[2][2]=='1'\
or k[0][0]=='1' and k[1][0]=='1' and k[2][0]=='1'\
or k[0][1]=='1' and k[1][1]=='1' and k[2][1]=='1'\
or k[0][2]=='1' and k[1][2]=='1' and k[2][2]=='1'\
or k[0][0]=='1' and k[1][1]=='1' and k[2][2]=='1'\
or k[2][0]=='1' and k[1][1]=='1' and k[0][2]=='1':
	print('Yes')
else:
    print('No')
N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
n = [0] * N
n[0] = 1
n[1] = 2

#listの中をinで探すのはくっそ遅い
if N == 1:
    print(1)
    exit()
if 1 in a and 2 in a:
    print(0)
    exit()
if 1 in a:
    n[0] = 0
    n[1] = 1
if 2 in a:
    n[1] = 0

for i in range(N - 2):
    if i + 3 in a:
        pass
    else:
        n[i + 2] = (n[i + 1] + n[i]) % 1000000007

print(n[N - 1])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
n = [0] * (N + 1)
n[0] = 1
n[1] = 1

#listの中をinで探すのはくっそ遅い
if 1 in a:
    n[1] = 0

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        n[i] = (n[i - 1] + n[i - 2]) % 1000000007

print(n[N])
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    n,k,s=map(int,input().split())
    ans=np.array([0]*n)
    ans[:k]+=s
    if s!=10**9:
        ans[k:]+=10**9
    else:
        ans[k:]+=10**9-1
    print(*ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    n,k,s=map(int,input().split())
    ans=np.array([0]*n)
    ans[:k]+=s
    if s!=10**9:
        ans[k:]+=10**9
    else:
        ans[k:]+=10**9-1
    print(*ans)

if __name__=='__main__':
    main()
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
c = list(map(int, input().split()))
c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
c = list(map(int, input().split()))

if N == 1:
    print(0)
    print(c[0])
    exit()

c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))
N = int(input())
s = [int(input()) for i in range(N)]
temp=s.copy()
s_max=max(temp)
temp=temp.remove(s_max)
s_max2=max(temp)

for i in range(N):
  if s[i]<s_max:
    print(s_max)
  else:
	print(s_max2)


### FIXED CODE ###

N=int(input())
s=[int(input()) for i in range(N)]

temp=s.copy()
s_max=max(temp)
temp.remove(s_max)
s_max2=max(temp)

for i in range(N):
  if s[i]<s_max:
    print(s_max)
  else:
    print(s_max2)
n, d, a = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
A.sort()
count = 0
for i in range(n):
    if A[i][1] > 0:
        sx = A[i][0]
        if A[i][1] % a == 0:
            count_a = A[i][1] // a
        else:
            count_a = A[i][1] // a +1
        A[i][1] -= count_a * a
        count += count_a
        for j in range(i+1, n):
            if A[j][1] > sx + d*2:
                break
            else:
                A[j][1] -= count_a * a
print(count)

### FIXED CODE ###

h, a = map(int, input().split())
count = 1
count += h // a
if h % a == 0:
    count -= 1
print(count)
s=input()
n=[int(c) for c in s]
 if int(s)%sum(n)==0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s=input()
nums=[int(c) for c in s]
if int(s)%sum(nums)==0:
    print('Yes')
else:
    print('No')
import math

ans = 0
ans += 0.5*k*(k+1)
# print(ans)

for a in range(1, k):
    for b in range(a+1,k+1):
        n = math.gcd(a, b)
        ans += n*6
        # print(a, b, n)

for i in range(1, k-1):
    for j in range(i+1, k):
        for k in range(j+1, k+1):
            d = math.gcd(i, j)
            ans += math.gcd(d, k)*6
            # print(i, j, k)

        #
        #
        # for c in range(b+1, k+1):
        #     ans += math.gcd(n, c)*3
        # print(a, b, c)

print(int(ans))

### FIXED CODE ###

k = int(input())

import math

ans = 0
ans += 0.5*k*(k+1)
# print(ans)

for a in range(1, k):
    for b in range(a+1,k+1):
        n = math.gcd(a, b)
        ans += n*6
        for c in range(b+1, k+1):
            if c != b:
                ans += math.gcd(n, c)*6

# for i in range(1, k-1):
#     for j in range(i+1, k):
#         for k in range(j+1, k+1):
#             d = math.gcd(i, j)
#             ans += math.gcd(d, k)*6

print(int(ans))
n,a,b=int(input()),[],[]
for i in range(1,n+1):
  for j in range(i,n+1):
    if i!=j and i+j!=n:
      a.append(i)
      b.append(j)
print(len(a))
for i,j in a,b:print(i,j)

### FIXED CODE ###

n,a,b=int(input()),[],[]
m=n+(n%2==0)
for i in range(1,n):
  for j in range(i+1,n+1):
    if i+j!=m:a.append(i);b.append(j)
l=len(a)
print(l)
for i in range(l):print(a[i],b[i])
import math
a, b, c, d = list(map(int, input().split()))
ans = []
for n in [a - 1, b]:
    mc = n // c
    md = n // d
    cd = c * d // math.gcd(c, d)
    mcd = n // cd
    ans.append(n - mc - md + mcd)
print(int(ans[1] - ans[0]))

### FIXED CODE ###

import fractions
a, b, c, d = list(map(int, input().split()))
ans = []
for n in [a - 1, b]:
    mc = n // c
    md = n // d
    cd = c * d // fractions.gcd(c, d)
    mcd = n // cd
    ans.append(n - mc - md + mcd)
print(int(ans[1] - ans[0]))
l=sorted(map(int,raw_input().split()))
print(l[0],l[1],l[2])

### FIXED CODE ###

l=list(map(int,input().split()))
L=sorted(l)
print(L[0],L[1],L[2])
n_k = [int(i) for i in input().split()]
n = n_k[0]
k = n_k[1]
r = n % k
r_1 = abs(r - k)
min = np.array([r, r_1]).min()
print(min)

### FIXED CODE ###

import numpy as np
n_k = [int(i) for i in input().split()]
n = n_k[0]
k = n_k[1]
r = n % k
r_1 = abs(r - k)
min = np.array([r, r_1]).min()
print(min)
n = int(input())

res = []
for i in range(n):
  city, value = input().split()
  value = int(value)
  res.append([city, value, i])
res_s = sorted(res, key = lambda x: (x[0], -x[1]))
for i in range(n):
  print(ans[i][2])

### FIXED CODE ###

n = int(input())

res = []
for i in range(n):
  city, value = input().split()
  value = int(value)
  res.append([city, value, i+1])
res_s = sorted(res, key = lambda x: (x[0], -x[1]))
for i in range(n):
  print(res_s[i][2])
from collections import OrderedDict
import math


def submit():
    a, b = map(int, input().split())
    s = min(a, b)
    l = max(a, b)

    if s == 1:
        print(1)
        return

    # 公約数を求める
    divisors = OrderedDict()
    for x in range(2, math.ceil(math.sqrt(s)) + 1):
        if s % x == 0 and l % x == 0:
            divisors[x] = True
    if l % s == 0:
        divisors[s] = True

    # ふるいにかけて素数のみ数える
    ans = 0
    lst = next(reversed(divisors))
    unprime = {}
    for d, v in divisors.items():
        if d not in unprime.keys():
            ans += 1
            c = 2*d
            while c <= lst:
                unprime[c] = 1
                c += d
    print(ans + 1)

        
if __name__ == "__main__":
    submit()    


### FIXED CODE ###


import math


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


def prime_fact(x):
    prime_pow = {}
    check_ceil = math.ceil(math.sqrt(x))
    for p in range(2, check_ceil + 1):
        p_cnt = 0
        while x % p == 0:
            x //= p
            p_cnt += 1
        if p_cnt:
            prime_pow[p] = p_cnt
    if x > 1:
        prime_pow[x] = 1
    return prime_pow


def submit():
    a, b = map(int, input().split())
    g = gcd(a, b)
    # gcdの素因数分解して素因数の数を求める
    p = prime_fact(g)
    print(len(p) + 1)


if __name__ == "__main__":
    submit()