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

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
check = [[] for i in range(N)]

for i in range(M):
    P[i], Y[i] = map(int, input().split())
    check[P[i]-1].append(Y[i])

for i in range(N):
    check[i].sort()

for i in range(M):
    tmp1 = ('00000' + str(P[i]))[-6:] 
    tmp2 = ('00000' + str(check[P[i]-1].index(Y[i])+1))[-6:]
    tmp = tmp1 + tmp2
    print(tmp)




### FIXED CODE ###

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
X = [0] * M
check = [[] for i in range(N)]

for i in range(M):
    P[i], Y[i] = map(int, input().split())
    X[i] = [Y[i], P[i], i]

X.sort()
#print(X)

count = [0] * (N+1)
ans_list = [[] for _ in range(M)]

for i in range(len(X)):
    count[X[i][1]] += 1
    tmp = ('000000'+ str(X[i][1]))[-6:] + ('000000'+ str(count[X[i][1]]))[-6:]
    ans_list[X[i][2]] = tmp

for i in range(len(ans_list)):
    print(ans_list[i])
### BUGGY CODE ###

if __name__ == '__main__':
    n, m = map(int, input().split())
    sweets = list(map(int, input().split()))

    cnt = 0
    total = 0
    totals = [0]
    for i in range(n):
        total += sweets[i]
        for old in totals:
            if (total - old) % m == 0:
                cnt += 1
        totals.append(total)
    
    print(cnt)

### FIXED CODE ###

import collections

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

b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]

d = collections.Counter(x % m for x in b)
ans = sum(v * (v - 1) // 2 for v in d.values())
print(ans)
### BUGGY CODE ###

from heapq import heapify, heappushpop

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

A = map(int, input("").split(" "))
A = list(A)
heapify(A)

for i in range(M):
    B, C = map(int, input("").split(" "))

    for j in range(B):
        if A[0] < C:
            heappushpop(A, C)
        else:
            break

c = 0
for a in A:
    c += a

print(c)


### FIXED CODE ###

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

A = map(int, input("").split(" "))
A = list(A)
A.sort()

potentials = []
for i in range(M):
    B, C = map(int, input("").split(" "))

    potentials.append((B, C))

potentials.sort(key=lambda x: x[1], reverse=True)

c = 0
for p in potentials:
    for b in range(p[0]):
        if p[1] > A[c]:
            A[c] = p[1]
            c += 1
            if c >= len(A):
                break
        else:
            break
    if c >= len(A):
        break

print(sum(A))
### BUGGY CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    """
    stack = deque()
    for i in range(H):
        tmp = list(input())
        for j in range(W):
            A[i][j] = tmp[j]
            if tmp[j] == "#":
                stack.append((i,j))
    """
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        #print(ans, stack)
        flag = False
        new_stack = deque()
        for a,b in stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
            if a != 0: # 上
                if A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
            if a != H-1: # 下
                if A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            if b != 0: # 左
                if A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            if b != W-1: # 右
                if A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()




### FIXED CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    #stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"]
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        #new_stack = deque()
        new_stack = []
        for a,b in stack:
        #while stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


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

n = int(input())
primes = [2]
for i in range(3, 100):
    flag = True
    for j in primes:
        if i%j==0:
            flag = False
            break
    if flag:
        primes.append(i)

factors = [0 for i in range(len(primes))]
def mul(x):
    if x==2:
        factors[0] += 1
        return 2
    else:
        tmp = x
        while tmp != 1:
            for i, prime in enumerate(primes):
                if tmp%prime==0:
                    factors[i] += 1
                    tmp = tmp//prime
                    break

        return x*mul(x-1)

mul(n)
num74 = 0
num24 = 0
num14 = 0
num4 = 0
num2 = 0
for factor in factors:
    if factor>=74:
        num74 += 1
    elif factor>=24:
        num24 += 1
    elif factor>=14:
        num14 += 1
    elif factor>=4:
        num4 += 1
    elif factor >=2:
        num2 += 1

ans = 0
''' 3 * 5 * 5 '''
tmp1 = num74+num24+num14+num4
tmp2 = num2
ans += tmp1*(tmp1-1)//2*tmp2 + tmp1*(tmp1-1)//2*(tmp1-2)
''' 5 * 15 '''
tmp1 = num74+num24+num14
tmp2 = num4
ans += tmp1*tmp2 + tmp1*(tmp1-1)
''' 3 * 25 '''
tmp1 = num74+num24
tmp2 = num14+num4+num2
ans += tmp1*tmp2 + tmp1*(tmp1-1)
''' 75 '''
tmp1 = num74
ans += tmp1
print(ans)


### FIXED CODE ###

n = int(input())
primes = [2]
for i in range(3, 100):
    flag = True
    for j in primes:
        if i%j==0:
            flag = False
            break
    if flag:
        primes.append(i)

factors = [0 for i in range(len(primes))]
def mul(x):
    #if x==2:
    #    factors[0] += 1
    #    return 2
    if x==1:
        return 1
    else:
        tmp = x
        while tmp != 1:
            for i, prime in enumerate(primes):
                if tmp%prime==0:
                    factors[i] += 1
                    tmp = tmp//prime
                    break

        return x*mul(x-1)

mul(n)
num74 = 0
num24 = 0
num14 = 0
num4 = 0
num2 = 0
for factor in factors:
    if factor>=74:
        num74 += 1
    elif factor>=24:
        num24 += 1
    elif factor>=14:
        num14 += 1
    elif factor>=4:
        num4 += 1
    elif factor >=2:
        num2 += 1

ans = 0
''' 3 * 5 * 5 '''
tmp1 = num74+num24+num14+num4
tmp2 = num2
ans += tmp1*(tmp1-1)//2*tmp2 + tmp1*(tmp1-1)//2*(tmp1-2)
''' 5 * 15 '''
tmp1 = num74+num24+num14
tmp2 = num4
ans += tmp1*tmp2 + tmp1*(tmp1-1)
''' 3 * 25 '''
tmp1 = num74+num24
tmp2 = num14+num4+num2
ans += tmp1*tmp2 + tmp1*(tmp1-1)
''' 75 '''
tmp1 = num74
ans += tmp1
print(ans)
### BUGGY CODE ###

import math

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

ls = []
ans = 0
answer = 0

for i in range(n-k+1):
    total = 0
    for j in range(k):
        j += i
        total += pp[j]
    if ans <= total:
        ans = max(ans, total)
        num = i

for n in range(k):
    ls.append(pp[num+n])

for i in range(len(ls)):
    answer += (1+ls[i])/2

print(answer)


### FIXED CODE ###

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

answer = sum(pp[:k])
total = sum(pp[:k])

for i in range(n-k):
    total = total - pp[i] + pp[i+k]
    answer = max(answer, total)

print((answer+k)/2)
### BUGGY CODE ###

def main():
    N = int(input())
    p = list(map(float,input().split()))
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j] += dp[i][j] * (1-p[i])
            dp[i+1][j+1] += dp[i][j] * p[i]
    print(sum(dp[N][N//2+1:]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    p = list(map(float,input().split()))
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j] += dp[i][j] * (1-p[i])
            dp[i+1][j+1] += dp[i][j] * p[i]
    print(sum(dp[N][N//2+1:]))


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

s = input()
ans = 0
num = 0
for i in range(num,len(s)-3):
    for j in range(i+4,len(s)):
        if  (int(s[i:j+1]) % 2019 == 0):
            ans += 1
            num = j
print(ans)

### FIXED CODE ###

s = input()
ans = 0
mod = [0]*2019
t = s[len(s)-1]
n = 1
for i in range(len(s)-1,-1,-1):
#     mod.append(int(s[i:])%2019)
    mod[int(t)%2019] += 1
#     t = int(t) + (10**(len(s)-i-1))*int(s[i])
    t = int(t) + n*10*int(s[i-1])
    n = n*10%2019
for i in range(0,2019):
    ans += mod[i]*(mod[i]-1)/2
ans += mod[0]
print(int(ans))
### BUGGY CODE ###

def binary_search(v, is_ok):
    """
    ソートしてから使え！！！
    v : list
        ある場所から左が条件を満たさず、右が条件を満たすように並んだ配列
    is_ok(x) : bool
        vの要素xが条件を満たすかどうかを返す関数
    """
    ng = -1             # 条件を満たさないiのうち今わかっている中で最大の値(v[0]が条件を満たすかもしれないので-1から)
    ok = len(v)         # 条件を満たすiのうち今わかっている中で最小の値(v[n-1]が条件を満たさないかもしれないのでnから)
    # okをできるだけ左に移動させてreturnする

    # ...... ng ok ......
    #          | ->
    # こうなるまで
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2

        if is_ok(v[mid]):   # v[mid]はokであることがわかった
            ok = mid        # okを左に移動
        else:               # v[mid]はngであることがわかった
            ng = mid        # ngを右に移動

    return ok



N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
X = [x for x, h in XH]
H = [(h + A - 1) // A for x, h in XH]

yuukou = 0
mou_mukou = [0] * N + [0]
ans = 0

# lを左端としてn個爆弾を使う
def bomb(l, n):
    global ans, yuukou
    ans += n
    yuukou += n
    r = l + 2 * D
    mou_mukou[binary_search(X, lambda x: r < x)] += n

for i in range(N):
    yuukou -= mou_mukou[i]
    H[i] -= yuukou
    if H[i] > 0:
        bomb(X[i], H[i])

print(ans)


### FIXED CODE ###

def binary_search(v, is_ok):
    """
    ソートしてから使え！！！
    v : list
        ある場所から左が条件を満たさず、右が条件を満たすように並んだ配列
    is_ok(x) : bool
        vの要素xが条件を満たすかどうかを返す関数
    """
    ng = -1             # 条件を満たさないiのうち今わかっている中で最大の値(v[0]が条件を満たすかもしれないので-1から)
    ok = len(v)         # 条件を満たすiのうち今わかっている中で最小の値(v[n-1]が条件を満たさないかもしれないのでnから)
    # okをできるだけ左に移動させてreturnする

    # ...... ng ok ......
    #          | ->
    # こうなるまで
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2

        if is_ok(v[mid]):   # v[mid]はokであることがわかった
            ok = mid        # okを左に移動
        else:               # v[mid]はngであることがわかった
            ng = mid        # ngを右に移動

    return ok



N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
X = [x for x, h in XH]
H = [(h + A - 1) // A for x, h in XH]

yuukou = 0
mou_mukou = [0] * N + [0]
ans = 0

# lを左端としてn個爆弾を使う
def bomb(l, n):
    global ans, yuukou
    ans += n
    yuukou += n
    r = l + 2 * D
    mou_mukou[binary_search(X, lambda x: r < x)] += n

for i in range(N):
    yuukou -= mou_mukou[i]
    H[i] -= yuukou
    if H[i] > 0:
        bomb(X[i], H[i])

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

#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        c,b = map(int, input().split())
        adj[c-1].append(b-1)
        adj[b-1].append(c-1)

    # 頂点1も含む
    res = [0]*n
    res[0] = 1

    def dfs(v, par, L):
        for nv in adj[v]:
            temp = L[:]
            if nv == par:
                continue
            if a[nv] > temp[-1]:
                temp.append(a[nv])
            else:
                temp[bisect_left(temp, a[nv])] = a[nv]
            res[nv] = len(temp)
            dfs(nv, v, temp)

    L = [a[0]]
    dfs(0, -1, L)
    for i in range(n):
        print(res[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        c,b = map(int, input().split())
        adj[c-1].append(b-1)
        adj[b-1].append(c-1)

    # 頂点1も含む
    res = [0]*n
    res[0] = 1

    def dfs(v, par, L):
        if v != 0:
            if a[v] > L[-1]:
                temp = -1
                L.append(a[v])
            else:
                temp = bisect_left(L, a[v])
                pre = L[temp]
                L[temp] = a[v]
        res[v] = len(L)
        for nv in adj[v]:
            if nv == par:
                continue
            dfs(nv, v, L)
        if v != 0:
            if temp == -1:
                L.pop(-1)
            else:
                L[temp] = pre

    L = [a[0]]
    dfs(0, -1, L)
    for i in range(n):
        print(res[i])

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

#300
N = int(input())
S = [input() for _ in range(N)]
L = []
S.sort()
Set = set(S)
SetL = list(Set)
SetL.sort()

for i in range(N):
    if i == 0:
        L.append(1)
    else:
        if S[i-1] == S[i]:
            L[len(L)-1] = L[len(L)-1] + 1
        else:
            L.append(1)

for i in range(len(L)):
    if L[i] == max(L):
        print(SetL[i])

### FIXED CODE ###

#300
N = int(input())
S = [input() for _ in range(N)]
L = [0 for _ in range(N)]
L1 = ["" for _ in range(N)]
S.sort()
k = 0


for i in range(N):
    if i == 0:
        L[k] = 1 
        L1[k] = S[i]
    else:
        if S[i-1] == S[i]:
            L[k] = L[k] + 1
        else:
            L[k+1] = 1
            L1[k+1] = S[i]
            k += 1

m = max(L)
for i in range(N):
    if L[i] == m:
        print(L1[i])
### BUGGY CODE ###

import math

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

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def primelist(n):
    P = [2]
    flag = 0
    for i in range(3,n+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    return(P)

def yakusuu(A):
    Y=[]
    for i in range(1,math.floor(math.sqrt(A+1))+1):
        if A%i==0:
            Y.append(i)
            Y.append(A//i)
    return(Y)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**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])

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

    return arr[-1][0]

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = factorization(N)
    pl = primelist(ms)
    ya = yakusuu(N)
    count=0
#    print(N,ms,pl,ya)
    for i in range(len(pl)):
        if pl[i] in ya:
            count+=1
    print(count)

### FIXED CODE ###

import collections

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

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

A,B=map(int, input().split())
N=gcd(A,B)
c = collections.Counter(prime_factorize(N))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
K=min(K, 30)
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    B=np.array(B)
    A=np.cumsum(B)[:N]
    if A.min()==N:
        break
    #print(B)
    
    
print(*A)


### FIXED CODE ###

#import numpy as np
N,K=map(int, input().split())

A=list(map(int, input().split()))
#K=min(K, 30)
for k in range(K):
    B=[0]*(N+1)
    for i in range(N):
        a=A[i]
        start=max(0,i-a)
        end=min(N,i+a+1)
        B[start]+=1
        B[end]-=1
    #B=np.array(B)
    A=[0]*N
    A[0]=B[0]
    for i in range(1,N):
        A[i]=A[i-1]+B[i]

    if min(A)==N:
        break
    #print(B)
    
    
print(*A)
### BUGGY CODE ###

n = int(input())
for i in range(1,3501):
  for j in range(1,3501):
    if 3*i*j == n * (i+j):
      print(n,i,j)
      exit()

### FIXED CODE ###

N = int(input())
for n in range(1, 3501):
    for w in range(n, 3501):

        try:
            t = (N*n*w) % (4*n*w - N*w - N*n)
        except:
            continue

        if t == 0 and 4*n*w - N*w - N*n>=0:
            print((N*n*w) // (4*n*w - N*w - N*n), n, w)
            exit()
### BUGGY CODE ###

#累積和による解法

N,Q = map(int, input().split())
S = input()
cnt_list = []

for i in range(N+1):
    S_part = S[:i]
    cnt = S_part.count("AC")
    cnt_list.append(cnt)
for j in range(Q):
    l,r = map(int, input().split())
    ans = cnt_list[r]-cnt_list[l-1]
    if S[l-1:l+1]=="CA":
        ans -= 1
    print(ans)


### FIXED CODE ###

#累積和による解法

N,Q = map(int, input().split())
S = input()
cnt_list = [0]

for i in range(1,N):
    if S[i]=="C" and S[i-1]=="A":
        cnt_list.append(cnt_list[-1]+1)
    else:
        cnt_list.append(cnt_list[-1])
for j in range(Q):
    l,r = map(int, input().split())
    ans = cnt_list[r-1]-cnt_list[l-1]
    print(ans)
### BUGGY CODE ###

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

maxg = 1
for i in range(2, M//N+1):
  if (M - N*i) % i == 0:
    maxg = i

print(maxg)

### FIXED CODE ###

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

i=1
while i <= M//N: 
  if M % i == 0:
    maxg = i
    if M//i <= M//N:
      maxg = M // i
      break
  i += 1

print(maxg)
### BUGGY CODE ###

import bisect
from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N,M = map(int,input().split())
    A = sorted(list(map(int,input().split())))
    que = deque(A)

    for _ in range(M):
        max_value = que.pop()
        bisect.insort_right(que,max_value // 2)

    print(sum(que))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    A = list(map(lambda x: x*(-1),A))

    heapq.heapify(A)

    for _ in range(M):
        max_value = heapq.heappop(A) * (-1)
        heapq.heappush(A,max_value//2 * (-1))

    print(sum(A) * (-1))

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

S=input()
Q=int(input())
Query=[[j for j in input().split()] for i in range(Q)]

c=0

for i in range(Q):
    if Query[i][0]=='1':
        c=c+1
    else:
        if ((Query[i][1]=='1')and(c%2==0)) or ((Query[i][1]=='2')and(c%2==1)):
            S=Query[i][2]+S
        else:
            S = S+Query[i][2]

if c%2==0:
    print(S)
else:
    print(''.join(list(reversed(S))))

### FIXED CODE ###

from collections import deque

S=input()
Q=int(input())
Query=[[j for j in input().split()] for i in range(Q)]

c=0
S0=deque(S)

for i in range(Q):
    if Query[i][0]=='1':
        c=c+1
    else:
        if ((Query[i][1]=='1')and(c%2==0)) or ((Query[i][1]=='2')and(c%2==1)):
            S0.appendleft(Query[i][2])
        else:
            S0.append(Query[i][2])

if c%2==0:
    print(''.join(S0))
else:
    print(''.join(reversed(S0)))
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    g = fractions.gcd(a, b)

    def search(n):
        i = 2
        so = []
        while n != 1 or i ** i <= n:
            while n % i == 0:
                n //= i
                so.append(i)
            i += 1
        if n != 1:
            so.append(n)

        return so

    ans = set(search(g))
    print(len(ans) + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    g = fractions.gcd(a, b)

    def search(n):
        i = 2
        so = []
        while not(n == 1 or i * i > n):
            while n % i == 0:
                n //= i
                so.append(i)
            i += 1
        if n != 1:
            so.append(n)

        return so

    ans = set(search(g))
    print(len(ans) + 1)


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

N = int(input())
a = {i+1: int(input()) for i in range(N)}

on = 1
ans = -1
count = 0
while True:
    on = a[on]
    count += 1
    if on == 2:
        ans = count
        break
    if on == 1:
        break
print(ans)


### FIXED CODE ###

N = int(input())
a = {i+1: int(input()) for i in range(N)}

on = 1
history = {1}
ans = -1
count = 0
while True:
    on = a[on]
    count += 1
    if on == 2:
        ans = count
        break
    if on in history:
        break
    history.add(on)
print(ans)