Harryxun/stf_run huggingface dataset:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# MOD = 10**9+7
# MOD = 998244353


def count(idx, s):
    left = right = 0
    for i in range(len(s)):
        if s[i] == "(":
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1

    return left, right, idx


n = int(input())
S = [input() for i in range(n)]
A = [count(i, s) for i, s in enumerate(S)]
A.sort(key=lambda x: (x[1], x[1]-x[0]))

left_rem = 0
for left, right in A:
    left_rem -= right
    if left_rem < 0:
        print("No")
        exit()
    left_rem += left

if left_rem == 0:
    print("Yes")
else:
    print("No")




### FIXED CODE ###

def count(i, s):
    left = right = 0
    for e in s:
        if e == "(":
            left += 1
        else:
            if left == 0:
                right += 1
            else:
                left -= 1

    return left-right, left, right, i


n = int(input())
S = [input() for i in range(n)]
s1 = []
s2 = []
for i, e in enumerate(S):
    c = count(i, e)
    # print(i, c)
    if c[0] >= 0:
        s1.append((c[2], c[3]))
    else:
        s2.append((-c[1], c[3]))

s1.sort()
s2.sort()
# print(s1, s2)
s = []
for e in s1:
    s.append(S[e[1]])
for e in s2:
    s.append(S[e[1]])
# print(s)

_, left, right, _ = count(0, "".join(s))
if left == right == 0:
    print("Yes")
else:
    print("No")
n=raw_input()
k=n.split(" ")

W=int(k[0])
H=int(k[1])
x=int(k[2])
y=int(k[3])
r=int(k[4])

if 0<=x-r<=W:
	if 0=<y-r<=H:
		print "Yes"
	else:
		print "No"
else:
	print "No"

### FIXED CODE ###


n=raw_input()
k=n.split(" ")

W=int(k[0])
H=int(k[1])
x=int(k[2])
y=int(k[3])
r=int(k[4])
f=0

if 0<=x-r<=x+r<=W:
  if 0<=y-r<=y+r<=H:
    print "Yes"
    f=1
if f==0:
  print "No"
A, B=int(input())
if A>=13:
    print(B)
elif 6<=A<=12:
    print(B/2)
else:
    print(0)

### FIXED CODE ###

A, B=map(int, input().split())
if A>=13:
    print(B)
elif 6<=A<=12:
    print(int(B/2))
else:
    print(0)
N = int(input())
# スペース区切りの整数の入力
A = list(map(int, input().split()))
A.sorted()

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

list_koyaku1=[]
list_koyaku11=[]       
         
if N==2:
    ans=max(A)

else:
    b=min(A)
    c=max(A)
    if gcd(c,b)==1:
        b=A[-2]
    
    for a in A:
        list_koyaku1.append(gcd(a,b))

    for a in list_koyaku1:
        list_koyaku11.append(gcd(a,c))
    
    number_prime=list_koyaku11.count(1)
    
    if number_prime>1:
        ans=1
    else:
        ans=max(list_koyaku11)

print(ans)



### FIXED CODE ###

N = int(input())
# スペース区切りの整数の入力
A = list(map(int, input().split()))


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

list1=[0]
L=0
for a in A:
    L=gcd(L,a)
    list1.append(L)

list2=[0]
R=0
for a in reversed(A):
    R=gcd(R,a)
    list2.append(R)

list2.reverse()

ans=[]

for i in range(N):
    ans.append(gcd(list1[i],list2[i+1]))

print(max(ans))
n, m = map(int, input().split())

ac = [0]*n
wa = [0]*n

for i in range(m):
    p, s = input().split()

    if s == 'WA' and ac[int(p)-1] == 0:
        wa[int(p)-1] += 1
    elif s == 'AC' and ac[int(p)-1] == 0:
        ac[int(p)-1] += 1

print('%d %d' % (sum(ac), sum([wa[k] for k in [i for i,j in enumerete(ac) if j != 0]])))

### FIXED CODE ###

N, M = map(int, input().split())
 
ac, wa = [0]*N, [0]*N
 
for i in range(M):
    p, s = input().split()
    if s == 'WA' and ac[int(p)-1] == 0:
            wa[int(p)-1] += 1
    elif s == 'AC' and ac[int(p)-1] == 0:
            ac[int(p)-1] += 1
print('%d %d' % (sum(ac), sum([wa[k] for k in [i for i, j in enumerate(ac) if j != 0]])))
N,T = map(int,input().split(' '))

List = []
 
for _ in range(N):
  list = list(map(int,input().split(' ')))
  List.append(list)
 
List = [x[0] for x in List if x[1]<=T]
  
print(min(List))

### FIXED CODE ###

N,T = map(int,input().split(' '))

clist = []
tlist = []

for _ in range(N):
  L = list(map(int,input().split(' ')))
  clist.append(L[0])
  tlist.append(L[1])
  
List = [c for c,t in zip(clist,tlist) if t<=T]

if len(List):
  print(min(List))
else:
  print('TLE')
n,q=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
ans=[0 for _ in range(n)]
def dfs(u,par):
    if par!=-1:
        ans[u]+=ans[par]
    for v in g[u]:
        if v==par:
            continue
        dfs(v,u)
for _ in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
dfs(0,-1)
print(*ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,q=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
ans=[0 for _ in range(n)]
def dfs(u,par):
    if par!=-1:
        ans[u]+=ans[par]
    for v in g[u]:
        if v==par:
            continue
        dfs(v,u)
for _ in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
dfs(0,-1)
print(*ans)
a, b, k = map(int, input().split())

if b-a+1 <=2k:
    for h in range(a, b+1):
        print(h)
else:
    for i in range(a, a+k):
        print(i)
    for j in range(b-k+1, b+1):
        print(j)


### FIXED CODE ###

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

if b-a+1 <= k*2:
    for h in range(a, b+1):
        print(h)

else:
    for i in range(a, a+k):
        print(i)
    for j in range(b-k+1, b+1):
        print(j)
def main ():
  N = int(input())
  A = list(map(int,input().split()))
  if 0 in A: 
    print (0)
  	return
  prod = 1 
  for a in A:
    prod *= a
 	if prod > 1000000000000000000:
  		print(-1) 
        return
	print(prod)
    
main()

### FIXED CODE ###

def main ():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A: 
        print (0)
        return
    prod = 1 
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod) 

main ()
n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
matc=list(0 for i in range(n+2*now))
mat2=list(0 for i in range(n+2*now))
for i in range(n):
  matc[now-a[i]]+=1
  mat2[now+a[i]]+=1
  now+=1
#print(matc)
for j in range(noww,noww+n+10):
  ans+=matc[j]*mat2[j]
print(ans)
       
       




### FIXED CODE ###

import numpy as np
n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
k=n+2*now
matc=[0]*(n+2)
mat2=[0]*(n+2)
for i in range(n):
  neg=i-a[i]
  pos=i+a[i]
  if neg>=0:
    matc[neg]+=1
  if pos<=n:
    mat2[pos]+=1
  now+=1
#print(matc)
for j in range(n+2):
  ans+=matc[j]*mat2[j]
print(ans)
n,l = map(int,input().split())
s = sorted[input() for _ in range(n)]
for i in range(n):
  print(*s,sep="")

### FIXED CODE ###

n,l = map(int,input().split())
s = [input() for _ in range(n)]
s_sorted = sorted(s)
for i in range(n):
  print(s_sorted[i],end="")
import sys
inputs = sys.stdin.readlines()
from functools import reduce
from operator import mul

n = int(inputs[0])
A = list(map(int, inputs[1].split()))
B = []
C = []
mod = 1000000007
for i in range(n):
    nb_rgb = [
        len([x for x in B if x == 0]),
        len([x for x in B if x == 1]),
        len([x for x in B if x == 2])
    ]
    tmp = [int(nb == A[i]) for nb in nb_rgb]
    if sum(tmp) == 1:
        B.append(tmp.index(1))
    elif sum(tmp) == 2:
        B.append(tmp.index(1))
        C.append(2)
    elif sum(tmp) == 3:
        B.append(tmp.index(1))
        C.append(3)

print(reduce(mul, C) % mod)

### FIXED CODE ###

import sys
inputs = sys.stdin.readlines()
from functools import reduce
from operator import mul

n = int(inputs[0])
A = list(map(int, inputs[1].split()))
B = {0:0, 1:0, 2:0}
C = []
mod = 1000000007
for i in range(n):
    matches = [int(nb == A[i]) for nb in B.values()]
    if sum(matches) == 1:
        B[matches.index(1)] += 1
    elif sum(matches) == 2:
        B[matches.index(1)] += 1
        C.append(2)
    elif sum(matches) == 3:
        B[matches.index(1)] += 1
        C.append(3)
    else:
        print(0)
        break
else:
    print(reduce(mul, C) % mod)
n, x, m = map(int, input().split())

dp = [-1]*(10**5+2)
nums = [-1]*(10**5+2)
nums[x] = 1
dp[0] = 0
dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    x = num[nex]
    if x >= n:
        print(r[n])
    else:
        print(r[-1])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex])
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )


### FIXED CODE ###

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

dp = [-1 for _i in range(10**5+2)]
nums = [-1 for _i in range(10**5+2)]
nums[x] = 1

dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    print(r[min(len(r)-1, n)])
elif n <= nums[bef]:
    print(r[n])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex]+1)
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )
S = input()
Q = int(input())
for i in range(Q):
    q = input()
    if q == '1':
        S = S[::-1]
    else:
        F, C = q.split()[1:]
        if F == '1':
            S = C + S
        else:
            S = S + C
print(S)

### FIXED CODE ###

S = input()
if 'A' in S and 'B' in S:
    print('Yes')
else:
    print('No')
N, M = map(int, input().split())

L = []
R = []
LR = [int(i) for i in range(1, N+1)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    LR.append(l)
    LR.append(r)

tmp = []
for gate in range(1, M+1):
    for i in range(L[gate-1], R[gate-1]+1):
        tmp.append(i)
    tmpLR = list(set(tmp) & set(LR))
    LR.clear()
    LR = tmpLR
    tmp.clear()

print(len(LR))

### FIXED CODE ###


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

L = []
R = []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

maxl = max(L)
minr = min(R)

ans = minr - maxl + 1
if ans > 0:
    print(ans)
else:
    print(0)
import collections
n = int(input())
l = list(int(x) for x in input().split())
el = []
ol = []
for i in range(n):
  if i % 2 == 0:
    el.append(l[i])
  else:
    ol.append(l[i])
e1 = collections.Counter(el).most_common()[0][0]
e2 = collections.Counter(el).most_common()[1][0]
o1 = collections.Counter(ol).most_common()[0][0]
o2 = collections.Counter(ol).most_common()[1][0]
cnt1 = 0
cnt2 = 0
if e1 != o1:
  for i in range(n//2):
    if el[i] != e1:
      cnt1 += 1
    if ol[i] != o1:
      cnt1 += 1
  print(cnt1)
else:
  for i in range(n//2):
    if el[i] != e1:
      cnt1 += 1
    if ol[i] != o2:
      cnt1 += 1
    if el[i] != e2:
      cnt2 += 1
    if ol[i] != o1:
      cnt2 += 1
  print(min(cnt1,cnt2))

### FIXED CODE ###

from collections import Counter

n = int(input())

e = []
o = []
for i, v in enumerate(input().split(' ')):
    if i % 2 == 0:
        e.append(int(v))
    else:
        o.append(int(v))

if len(set(e + o)) == 1:
    print(int(len(e + o) / 2))
    exit()

if Counter(o).most_common()[0][0] == Counter(e).most_common()[0][0]:
    ans = min(len(o) - Counter(o).most_common()[1][1] + len(e) - Counter(e).most_common()[0][1], len(o) - Counter(o).most_common()[0][1] + len(e) - Counter(e).most_common()[1][1])
    print(ans)
else:
    print(len(o) - Counter(o).most_common()[0][1] + len(e) - Counter(e).most_common()[0][1])
N=int(input())
if N>=2 and N<=10**5:
    array=list(map(int,input().strip().split()))
    if array[0]>=0 and array[-1]<=10**18:
        multipul=1
        for i in len(array-1):
            multipul=multipul*array[i]
        print(multipul)

### FIXED CODE ###

n = int(input())
m = list(map(int, input().split()))
ans = 1
if min(m) == 0:
    print(0)
else:
    m.sort(reverse=True)
    for i in m:
        ans *= i
        if ans > 1000000000000000000:
            ans = -1
            break
    print(ans)
import numpy as np

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

e = np.eye(n + 1, dtype=int)
for i in range(n - 1):
    a, b = map(int, input().split())
    e[a][b] = 1

for i in range(1, n):
    for j in range(i+1,n):
        if e[i][j] == 1:
            e[i][j+1:] += e[j][j + 1:]
        else:
            continue

point = np.zeros(n, dtype=int)
for i in range(q):
    p, x = map(int, input().split())
    point[p - 1] += x
ans = np.dot(point, e[1:, 1:])
print(*ans)

### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
tree = [[] for _ in range(n+1)]
cnt = [0] * (n+1)

for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    cnt[p] += x

queue = deque([1])
visited = {1}
while queue:
    now = queue.popleft()
    visited.add(now)
    for t in tree[now]:
        if t in visited:
            pass
        else:
            queue.append(t)
            cnt[t] += cnt[now]

print(*cnt[1:])
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [""]*(N+1)
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(2, N+1):
        cur = (int(dp[i]) if dp[i] else 0)
        for a in A:
            if match[a] == i or dp[i - match[a]]:
                ne = int(dp[i - match[a]] + str(a))
                if cur < ne:
                    dp[i] = str(ne)
                    cur = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = ["-"]*(N+10)
    dp[0] = ""
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(N+1):
        if dp[i] == "-":
            continue
        for a in A:
            cur = dp[i+match[a]]
            ne = dp[i] + str(a)
            if len(cur) < len(ne) or cur < ne:
                dp[i+match[a]] = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()
S, T = input().split("\n")

cnt = []
for i in range(len(S)-len(T)+1):
	mismatch = 0
	for j in range(len(T)):
		if S[i+j] != T[j]:
			mismatch += 1
	cnt.append(mismatch)
	
print(min(cnt))

			

### FIXED CODE ###

S = input()
T = input()
  
cnt = []
for i in range(len(S)-len(T)+1):
	mismatch = 0
	for j in range(len(T)):
		if S[i+j] != T[j]:
			mismatch += 1
	cnt.append(mismatch)
	
print(min(cnt))
a = int(input())
b = int(input())

ab = a*b
if ab%2 == 0:
  print("Even")
else:
  print("Odd")


### FIXED CODE ###

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

if a*b%2 == 0:
  print("Even")
else:
  print("Odd")
from collections import Counter
from scipy.misc import comb
N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]
ans = 0
for count in Counter(s).values():
    ans += comb(count, 2, exact=True)
print(ans)

### FIXED CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]
ans = 0
for count in Counter(s).values():
    ans += comb(count, 2, exact=True)
print(ans)
k = int(input())
s = input()

if len(s) <= k:
  print(s)
else:
  print(s[:k] + ...)

### FIXED CODE ###

k = int(input())
s = input()

if len(s) <= k:
  print(s)
else:
  print(s[:k] + "...")
def d_snuke_numbers(K):
    candidate = []
    for k in range(20):
        for l in range(1, 10):
            candidate.append(str(l)+str(9)*k)
    ans = []
    for k in range(K):
        ans.append(candidate[k])
    ans = '\n'.join(ans)
    return ans

K = int(input())
print(d_snuke_numbers(K))

### FIXED CODE ###

def d_snuke_numbers(K):
    import math

    def ns(n):  # n/S(n)の計算
        return n / sum(map(int, list(str(n))))

    def f(n):  # n<=xの中で ns(x) を最小にするような最小の値xを求める
        digit = len(str(n))
        # n自身も候補の1つである
        min_ns = ns(n)
        ret = n
        for d in range(digit + 1):
            x = (10**(d+1)) * math.floor(n / (10**(d+1)) + 1) - 1
            s = ns(x)
            if min_ns > s:
                min_ns = s
                ret = x
        return ret

    n = 0
    candidate = []
    for _ in range(K):
        n = f(n + 1)
        candidate.append(n)
    ans = '\n'.join(map(str, candidate))
    return ans

K = int(input())
print(d_snuke_numbers(K))
while True:
	n, x = map(int, raw_input().split())
	if n == 0 and x == 0:
		break

	a = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			b = x - (i + j)
			if b > j and b <= n:
				a += 1
	print(a)

### FIXED CODE ###

while True:
	n, x = map(int, input().split())
	if n == 0 and x == 0:
		break

	ans = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			a = x - (i + j)
			if j < a <= n:
				ans += 1
	print(ans)
from heapq import heappop, heappush

x, y, a, b, c = map(int, input().split())
apple = []
for p in map(int, input().split()):
  heappush(apple, (-p, True))
for q in map(int, input().split()):
  heappush(apple, (-q, False))
for r in map(int, input().split()):
  heappush(apple, (-r, None))
delicious = 0
colorless = 0
while x + y > colorless:
  minus_taste, color = heappop(apple)
  if color is True:
    if x > 0:
      delicious -= minus_taste
      x -= 1
  elif color is False:
    if y > 0:
      delicious -= minus_taste
      y -= 1
  else:
    delicious -= minus_taste
    colorless += 1
print(delicious)

### FIXED CODE ###

from heapq import heappop, heappush

x, y, a, b, c = map(int, input().split())
apple = []
# Red is 0, Green is 1, Colorless is 2
for p in map(int, input().split()):
  heappush(apple, (-p, 0))
for q in map(int, input().split()):
  heappush(apple, (-q, 1))
for r in map(int, input().split()):
  heappush(apple, (-r, 2))
delicious = 0
colorless = 0
while x + y > colorless:
  minus_taste, color = heappop(apple)
  if color == 0:
    if x > 0:
      delicious -= minus_taste
      x -= 1
  elif color == 1:
    if y > 0:
      delicious -= minus_taste
      y -= 1
  else:
    delicious -= minus_taste
    colorless += 1
print(delicious)
from collections import deque

inf = float('inf')
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

# bfs
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#':
            continue
        dist = [[inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0]
            j = q[1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '#':
                    continue
                update(ni, nj, dist[i][j] + 1)
        
for i in range(h):
    for j in range(w):
        if dist[i][j] == inf:
            continue
        ans = max(ans, dist[i][j])

print(ans)

### FIXED CODE ###

from collections import deque

inf = float('inf')
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0

# bfs
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#':
            continue
        dist = [[-inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != -inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0][0]
            j = q[0][1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '#':
                    continue
                update(ni, nj, dist[i][j] + 1)

        # 2次元配列のmax
        dist_max = max(list(map(lambda x: max(x), dist)))
        ans = max(ans, dist_max)

print(ans)
from fractions
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return divisors
  
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
 
A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(fractions.gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)

### FIXED CODE ###

from fractions import gcd
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return divisors
  
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, int(n**0.5)+1):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
 
A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)
def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)


def main():
    INF = float('inf')

    N, M = map(int, input().split())
    keys = [read_key() for _ in range(M)]

    dp = [[INF] * (1 << N) for _ in range(M + 1)]

    dp[0][0] = 0
    for i in range(M):
        a, m = keys[i]
        dpi = dp[i]
        dpi1 = dpi[i + 1]
        for j in range(1 << N):
            if dpi[j] == INF:
                continue
            if dpi[j] + a < dpi1[j | m]:
                dpi1[j | m] = dpi[j] + a
            if dpi[j] < dpi1[j]:
                dpi1[j] = dpi[j]

    if dp[M][(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[M][(1 << N) - 1])


main()


### FIXED CODE ###

def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)


def main():
    INF = float('inf')

    N, M = map(int, input().split())
    keys = [read_key() for _ in range(M)]

    dp = [[INF] * (1 << N) for _ in range(M + 1)]

    dp[0][0] = 0
    for i in range(M):
        a, m = keys[i]
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(1 << N):
            if dpi[j] == INF:
                continue
            if dpi[j] + a < dpi1[j | m]:
                dpi1[j | m] = dpi[j] + a
            if dpi[j] < dpi1[j]:
                dpi1[j] = dpi[j]

    if dp[M][(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[M][(1 << N) - 1])


main()