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

Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
prime = primes(maxr)
prime2 = [0 for i in range(maxr+1)]
for i in prime:
    if (i+1)/2 in prime:
        prime2[i] += 1
for i in range(maxr):
    prime2[i+1] += prime2[i]
for l,r in lr:
    print(prime2[r]-prime2[l-1])
    
    

### FIXED CODE ###

Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(3,n + 1) if is_prime[i] and is_prime[(i+1)//2]]
prime = primes(maxr)
import bisect
for l,r in lr:
    print(bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1))
### BUGGY CODE ###


import math

K = int(input())

gcd = []

for a in range(1,K+1,1):
    for b in range(1,K+1,1):
        for c in range(1,K+1,1):
            partial = math.gcd(a, b)
            ans = math.gcd(partial, c)
            gcd.append(ans)

print(sum(gcd))

### FIXED CODE ###


import math

K = int(input())

gcd = []

for a in range(1,K+1,1):
    for b in range(1,K+1,1):
        for c in range(1,K+1,1):
            partial = math.gcd(a, b)
            ans = math.gcd(partial, c)
            gcd.append(ans)

print(sum(gcd))
### BUGGY CODE ###

s = input()
q = int(input())

for _ in range(q):
  qq = list(map(str, input().split()))
  if qq[0] == "1":
    s = s[::-1]
  else:
    if qq[1] == "1":
      s = qq[2] + s
    else:
      s = s + qq[2]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
q = int(input())

rev = 0
for i in range(q):
  tfc = list(input().split())
  if tfc[0] == "1":
    rev = abs(rev-1)
  else:
    t,f,c = tfc
    if rev:
      if f == "1":
        s.append(c)
      else:
        s.appendleft(c)
    else:
        if f == "1":
          s.appendleft(c)
        else:
          s.append(c)
if rev:
  t = []
  for i in range(len(s)):
    t.append(s.pop())
  print("".join(t))
else:
  print("".join(s))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
edge = [list(map(int,input().split())) for i in range(N-1)]

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

K = 0
for g in graph:
    K = max(K,len(g))
print(K)

color = [[] for i in range(N)]
L = []
i = 0
for e in edge:
    while True:
        if i%K not in color[e[0]-1] and i%K not in color[e[1]-1]:
            L.append(i%K)
            color[e[0]-1].append(i%K)
            color[e[1]-1].append(i%K)
            break
        i += 1


for l in L:
    print(l+1)

### FIXED CODE ###

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

N = int(input())
edge = [list(map(int,input().split())) for i in range(N-1)]

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)

queue = deque()
queue.append(0)

color = [-1 for _ in range(N)]

k = 0

while queue:
    c = 0
    node = queue.popleft()
    for adj in graph[node]:
        if color[node] == c:
            c += 1
        color[adj] = c
        k = max(k,c+1)
        c += 1
        queue.append(adj)
print(k)

for e in edge:
    print(color[e[1]-1]+1)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

#時間計測テスト

s = str(input())
K = I()
n = len(s)

a = []
for i in range(n):
    for j in range(i+1,n+1):
        a.append(s[i:j])

a.sort()
num = 0
used = []
for i in range(len(a)):
    if a[i] in used:
        continue
    else:
        num += 1
        used.append(a[i])
        if num == K:
            print(a[i])
            exit()

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

s = str(input())
K = I()
n = len(s)

a = set()
for i in range(n):
    for j in range(i+1,min(i+6,n+1)):
        a.add(s[i:j])

a = list(a)
a.sort()
print(a[K-1])
### BUGGY CODE ###

N, X, M = [int(x) for x in input().split()]

seen = set()
front = []
cycle = []
for i in range(N):
    x = pow(X, 2 ** i, M)
    if x in seen:
        index = front.index(x)
        front, cycle = front[:index], front[index:]
        break
    front.append(x)
    seen.add(x)


if N <= len(front):
    print(sum(front[:N]))
    exit()

if N <= len(front) + len(cycle):
    print(sum(front) + sum(cycle[: N - len(front)]))
    exit()

q, r = divmod(N - len(front), len(cycle))

if False:
    A = [pow(X, 2 ** i, M) for i in range(N)]
    B = front + cycle * q + cycle[:r]
    print(A, B)
    assert A == B
print(sum(front) + sum(cycle) * q + sum(cycle[:r]))


### FIXED CODE ###

def solve(N, X, M):
    seen = set()
    front = [X]
    cycle = []
    for i in range(N - 1):
        x = (front[-1] * front[-1]) % M
        if x in seen:  # seen can't be more than M since x is < M
            index = front.index(x)
            front, cycle = front[:index], front[index:]
            break
        front.append(x)
        seen.add(x)
    if N <= len(front):
        return sum(front[:N])

    if N <= len(front) + len(cycle):
        return sum(front) + sum(cycle[: N - len(front)])

    q, r = divmod(N - len(front), len(cycle))

    if False:
        A = [pow(X, 2 ** i, M) for i in range(N)]
        B = front + cycle * q + cycle[:r]
        print(A, B)
        assert A == B
    return sum(front) + sum(cycle) * q + sum(cycle[:r])


N, X, M = [int(x) for x in input().split()]
print(solve(N, X, M))
### BUGGY CODE ###

#ABC066C
import pprint
n = int(input())
ai = list(map(int, input().split()))
bi = []
for a in ai:
    bi.append(a)
    bi.reverse()
for b in bi:
    print(b, end=" ")

### FIXED CODE ###

#ABC066C
import pprint
n = int(input())
ai = list(map(int, input().split()))
bi = []
ran = 0
if n%2==0:
    for i in range(n//2):
        bi.append(ai[i+i+1])
    bi.reverse()
    for i in range(n//2):
        bi.append(ai[i+i])
else:
    for i in range(n//2+1):
        bi.append(ai[i+i])
    bi.reverse()
    for i in range(n//2):
        bi.append(ai[i+i+1])
        
for b in bi:
    print(b, end=" ")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# なんかおかしい！！
import math
import sys
import itertools
import numpy as np


# なんこか入力
x,y,z,k = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort()
b.sort()
c.sort()
#cake = [[0 for i in range(3)] for j in range(3000)]
#cake[0][0]=x-1
#cake[0][1]=y-1
#cake[0][2]=z-1
#print(a[x-1]+b[y-1]+c[z-1])
#print(a[cake[0][0]],b[cake[0][1]],c[cake[0][2]])
s = [[x-1,y-1,z-1]]
t = [[x-1,y-1,z-1]]
#print(s)

for i in range(0,k):
    ma = 0
    temp = [-1,-1,-1]
    for j in s:
        if ma <= a[j[0]]+b[j[1]]+c[j[2]] :
            temp = j
            ma = a[j[0]]+b[j[1]]+c[j[2]]
#    print(temp)
    print(a[temp[0]]+b[temp[1]]+c[temp[2]])
#    print(a[temp[0]],b[temp[1]],c[temp[2]])
    s.remove(temp)
#    print("s=",s)
#    print("t=",t)
#    print(temp)
    if temp[0] > 0:
        if [temp[0]-1,temp[1],temp[2]] in t:
            pass
        else:
            s.append([temp[0]-1,temp[1],temp[2]])
            t.append([temp[0]-1,temp[1],temp[2]])
    if temp[1] > 0:
        if [temp[0],temp[1]-1,temp[2]] in t:
            pass
        else:
            s.append([temp[0],temp[1]-1,temp[2]])
            t.append([temp[0],temp[1]-1,temp[2]])
    if temp[2] > 0:
        if [temp[0],temp[1],temp[2]-1] in t:
            pass
        else:
            s.append([temp[0],temp[1],temp[2]-1])
            t.append([temp[0],temp[1],temp[2]-1])



### FIXED CODE ###

# -*- coding: utf-8 -*-
# ヒープキューを使う

import math
import sys
import itertools
import numpy as np
import heapq
 
# なんこか入力
x,y,z,k = map(int, input().split())
 
# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort()
b.sort()
c.sort()

h = [] # heap
g = set() #使用済み

heapq.heappush(h,(-(a[x-1]+b[y-1]+c[z-1]),x-1,y-1,z-1))
g.add((x-1,y-1,z-1))

#print(h)

for i in range(k):
#    heapq.heapify(h)
    temp =[]
    temp = heapq.heappop(h)
    print(-temp[0])
    for j in range(3):
        if temp[j+1]==0:
            continue
        if j == 0:
            temp2 = (-(a[temp[1]-1]+b[temp[2]]+c[temp[3]]),temp[1]-1,temp[2],temp[3])
        elif j == 1:
            temp2 = (-(a[temp[1]]+b[temp[2]-1]+c[temp[3]]),temp[1],temp[2]-1,temp[3])
        else:
            temp2 = (-(a[temp[1]]+b[temp[2]]+c[temp[3]-1]),temp[1],temp[2],temp[3]-1)
        if (temp2[1],temp2[2],temp2[3]) in g:
            continue
        heapq.heappush(h,temp2)
        g.add((temp2[1],temp2[2],temp2[3]))
### BUGGY CODE ###

import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,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=eratosu(10**6+10)
@lru_cache(maxsize=10**10)
def bunkai(n):
    if n==1:return []
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen={i:0 for i in PRIME}
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l[0] 
        if now==1:continue
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen.values())!=n:
    print("setwise coprime")
else:
    print("not coprime")

#print(seen)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
def Dlist(BIG):
    D=[1]*(BIG+1)
    for p in range(2,BIG+1):
        if D[p]!=1:
            continue
        for i in range(p,BIG+1,p):
            if D[i]==1:
                D[i]=p
    return D

D=Dlist(max(A))
def SOINSU(num,D): #素因数だけ列挙(setしただけ)
    now=num ; ans=set()
    while now>1:
        ans.add(D[now])
        now//=D[now]
    return ans

seen=[0]*(10**6+10)
flag=1
for num in A:
    for i in SOINSU(num,D):
        if seen[i]!=0: flag=0
        seen[i]+=1
if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###



n, k= [0] * 2
p = []

def format_input(filename = None):
	global n, k
	global p
	if filename == None:
		n, k = list(map(int, input().split()))
		p = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 2 * 10**5)
		k = rng(1, n)
		p = [rng(1, 10**3) for i in range(n)]

def get_answer():
	e = []
	for i in range(n - k + 1):
		e.append(sum(p[i:i+k]))
	e.sort()
	answer = float(e.pop() + k) / 2.0
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)


### FIXED CODE ###



n, k= [0] * 2
p = []

def format_input(filename = None):
	global n, k
	global p
	if filename == None:
		n, k = list(map(int, input().split()))
		p = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 2 * 10**5)
		k = rng(1, n)
		p = [rng(1, 10**3) for i in range(n)]

def get_answer():
	e = []
	e.append(sum(p[0:k]))
	for i in range(n - k):
		e.append(e[i]-p[i]+p[i+k])
	e.sort()
	answer = float(e.pop() + k) / 2.0
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)
### BUGGY CODE ###

N = int(input())
A_lis = list(input().split())
count = 1
r = 10 ** 9 + 7

for i in range(N):
    if N % 2 == i % 2:
        if A_lis.count(str(i)) != 0:
            count = 0
            break
        else:
            continue
    else:
        if i == 0:
            if A_lis.count(str(i)) == 1:
                continue
            else:
                count = 0
                break
        elif A_lis.count(str(i)) != 2:
            count = 0
            break
        else:
            count = (count * 2) % r
            continue
        
print(count)


### FIXED CODE ###

import numpy as np
from collections import Counter
mo = 1000000007
r = range
 
n = int(input())
a = np.array(list(map(int, input().split())))
 
c = Counter(a.tolist())
 
if n % 2 == 1 and (0 not in c or c[0] != 1): print(0); exit();
 
for i in r(n//2):
    x = i * 2 + (1 if n % 2 == 0 else 2)
    if x not in c or c[x] != 2: print(0); exit();
 
print(2 ** (n//2) % mo)
### BUGGY CODE ###

n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

dp = [0] * (n + 1)
for i in range(1, n+1):
    feat = [i]
    if i - ga >= 0:
        feat.append(dp[i-ga]+gb)
    if i - sa >= 0:
        feat.append(dp[i-sa]+sb)
    if i - ba >= 0:
        feat.append(dp[i-ba]+bb)
    dp[i] = max(feat)

B = dp[-1]
dp = [0] * (B + 1)
for i in range(1, B+1):
    feat = [i]
    if i - gb >= 0:
        feat.append(dp[i-gb]+ga)
    if i - sb >= 0:
        feat.append(dp[i-sb]+sa)
    if i - bb >= 0:
        feat.append(dp[i-bb]+ba)
    dp[i] = max(feat)
print(dp[-1])


### FIXED CODE ###

n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

dp1 = [0] * (n + 1)
if n > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp[i] = max(feat)
    for i in range(5001, n+1):
        dp1[i] = max(i, dp1[i-ga]+gb, dp1[i-sa]+sb, dp1[i-ba]+bb)
else:
    for i in range(1, n+1):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp1[i] = max(feat)

B = dp1[-1]
dp2 = [0] * (B + 1)
if B > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

    for i in range(5001, B+1):
        dp2[i] = max(i, dp2[i-gb]+ga, dp2[i-sb]+sa, dp2[i-bb]+ba)
else:
    for i in range(1, B+1):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

print(dp2[-1])
### BUGGY CODE ###

import numba
from numba import njit, b1, i4, i8, f8
import numpy as np  # noqa

N = int(input())
A = np.array([int(x) for x in input().split()], dtype=np.int32)


@njit((i4[:], ), cache=True)
def main(A):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            ans = (ans + A[i] * A[j]) % (10**9 + 7)
    return ans


print(main(A))


### FIXED CODE ###

import numba
from numba import njit, b1, i4, i8, f8
import numpy as np  # noqa

N = int(input())
A = [int(x) for x in input().split()]


def main(A):
    ans = 0
    s = 0
    for i in range(N - 2, -1, -1):
        s += A[i + 1]
        s %= 10**9 + 7
        ans = (ans + A[i] * s) % (10**9 + 7)
    return ans


print(main(A))
### BUGGY CODE ###

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

for i in range(1, x+1):
    w, v = map(int, input().split())
    for j in range(y+1):
        num0 = dp[i-1][j]
        if j-w >= 0:
            num1 = dp[i-1][j-w]+v
            if num1 > num0:
                dp[i][j] = num1
            else:
                dp[i][j] = num0
        else:
            dp[i][j] = num0
print(max(dp[-1]))


### FIXED CODE ###

def num():
    x, y = map(int, input().split())
    dp = [0]*(y+1)

    for i in range(x):
        w, v = map(int, input().split())
        for j in range(y, w-1, -1):
            num = dp[j-w]+v
            if num > dp[j]:
                dp[j] = num
    print(dp[-1])

num()
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split()))
    hs = [int(input()) for i in range(N)]
    hs.sort()
    i = 0
    r = 10 ** 9
    while True:
        if i + K > N:
            break
        r = min(r, max(hs[i:i + K]) - min(hs[i:i + K]))
        i += 1
    print(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = list(map(int, input().split()))
    hs = [int(input()) for i in range(N)]
    hs.sort()
    i = 0
    r = 10 ** 9
    while True:
        if i + K > N:
            break
        r = min(r, hs[i + K - 1] - hs[i])
        i += 1
    print(r)


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

#ABC 144 C - Walk on Multiplication Table
N = int(input())

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
from itertools import combinations
import functools
import operator
P = prime_factorize(N)
m = N+1
memo = []
for i in range(1,len(P)+1):
    L1 = list(combinations(P,i))
    L1 = [list(l) for l in L1]
    for l in L1:
        if l not in memo:
            memo.append(l)
            s1 = functools.reduce(operator.mul,l)
            s2 = N/s1
            if s1+s2 <=m:
                m = s1+s2
print(int(m-2))

### FIXED CODE ###

N = int(input())
ans = N*3
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        s1 = i
        s2 =N/i
        
        if ans > s1+s2:
            ans =int(s1+s2)
print(ans-2)
### BUGGY CODE ###

cnt = 0
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    for j in range(i+1, N):
        if j - i == A[i] + A[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter
cnt = 0
N = int(input())
A = list(map(int, input().split()))
minus_list = [j - A[j] for j in range(N)]
counter = Counter(minus_list)
for i in range(N):
    add = A[i] + i
    cnt += counter[add]
print(cnt)
### BUGGY CODE ###

def edu_dp_e_knapsack2():
    n, c = map(int, input().split())
    w, v = [0], [0]
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[float('inf')] * 100001 for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1, n+1):
        for j in range(0, 100001):
            dp[i][j] = dp[i-1][j]
            if j >= v[i]:
                dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]]+w[i])
    ans = 100000
    while dp[n][ans]>c:ans-=1
    print(ans)
edu_dp_e_knapsack2()

### FIXED CODE ###

def edu_dp_e_knapsack2():
    n, c = map(int, input().split())
    w, v = [0], [0]
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[float('inf')] * 100001 for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(0, 100001):
            dp[i][j] = dp[i - 1][j]
            if j >= v[i]:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i])
    ans = 100000
    while dp[n][ans] > c: ans -= 1
    print(ans)
edu_dp_e_knapsack2()
### BUGGY CODE ###

import math


def cf(x1, x2):
    ret = []
    for i in range(1, min(x1, x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            ret.append(i)
    return ret


def is_prime_number(num):
    if num == 1:
        return False

    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i += 1
    return True


def check(num):
    if num == 1:
        return True
    else:
        return is_prime_number(num)


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

    count_set = set()

    for i in range(len(common_divisor_list) - 1):
        for j in range(i+1, len(common_divisor_list)):
            if check(common_divisor_list[i]) and check(common_divisor_list[j]):
                # print(common_divisor_list[i], common_divisor_list[j])
                count_set.add(common_divisor_list[i])
                count_set.add(common_divisor_list[j])

    if len(common_divisor_list) == 1:
        count_set.add(1)

    print(len(count_set))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


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


def gcd(a, b):
    if a > b:
        a, b = (b, a)
    while b:
        a, b = b, a % b
    return a


def main():
    a, b = map(int, input().split())
    gcd_num = gcd(a, b)
    c = collections.Counter(prime_factorize(gcd_num))
    # print(prime_factorize(gcd_num))
    # cには１が含まれていないので、その分カウントを増やす
    print(len(c) + 1)


if __name__ == '__main__':
    main()