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

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



from copy import deepcopy
@mt
def slv(N, S, A):

    memo = [Counter() for _ in range(S+1)]
    memo[0] = {0:1}
    for a in A:
        nm = []
        for s in range(S+1):
            nm.append(deepcopy(memo[s]))
        for s in range(S+1):
            if s + a <= S and len(memo[s]) > 0:
                for k, v in memo[s].items():
                    nm[s+a][k+1] += v
        memo = nm

    mod = 998244353
    ans = 0
    for k, m in memo[S].items():
        l = m * 2**(N-k)
        ans += l
        ans %= mod




    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S, A):
    mod = 998244353
    memo = [0] * (S+1)
    memo[0] = 1
    for a in A:
        nm = [2*memo[s] % mod for s in range(S+1)]
        for s in range(S+1-a):
                nm[s+a] += memo[s]
                nm[s+a] %= mod
        memo = nm

    return memo[S]


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


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

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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

rli = []
for i in range(q):
    l, r = map(int, input().split())
    l, r = l, r
    rli.append((r, l, i))
rli.sort()

last = [-1] * (n + 1)

bit = Bit(n)
ans = [0] * q
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
for i in ans:
    print(i)


### FIXED CODE ###

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 2)]
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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

rli = []
for i in range(q):
    l, r = map(int, input().split())
    rli.append((r, l, i))
rli.sort(key=lambda x: x[0])

last = [-1 for _ in range(n + 1)]

bit = Bit(n)
ans = [-1 for _ in range(q)]
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep="\n")
### BUGGY CODE ###

def main():
    n = int(input())
    a = input().split()
    ans = []
    add = ans.append
    rev = ans.reverse
    for i in range(n):
        add(a[i])
        rev()
    print(" ".join(ans))
if __name__=="__main__": main()

### FIXED CODE ###

def main():
    n = int(input())
    a = input().split()
    if n%2: ans = a[n-1::-2] + a[1:n-1:2]
    else: ans = a[n-1:0:-2] + a[0:n-1:2]
    print(" ".join(ans))
if __name__=="__main__": main()
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

E = 0
max = 0
for i in range(N - K + 1):
    work = sum(P[i:i+K])
    if work > max:
        max = work
        max_values = P[i:i+K]

for m in max_values:
    E += (1 + m) * (1/2)

print(E)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P_E = list(((1 + P[i]) / 2) for i in range(N))

E = 0
prog = sum(P_E[0:K])
max = prog
for i in range(N - K):
    prog += P_E[i + K] - P_E[i]
    if prog > max:
        max = prog
    else:
        pass
    
print(max)
### BUGGY CODE ###

from collections import deque

n = int(input())

q = deque()
for i in range(n):
    cmd = input().strip()
    if cmd == 'deleteFirst':
        q.popleft()
        continue
    if cmd == 'deleteLast':
        q.pop()
        continue
    cmd, x = cmd.split()
    if cmd == 'insert':
        q.appendleft(x)
        continue
    if cmd == 'delete':
        try:
            q.remove(x)
        except:
            pass
        continue

print(' '.join(q))

### FIXED CODE ###

import sys
from collections import deque

n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    cmd = sys.stdin.readline()[:-1]
    if cmd[0] == 'i':
        q.appendleft(cmd[7:])
    elif cmd[6] == ' ':
        try:
            q.remove(cmd[7:])
        except:
            pass
    elif cmd[6] == 'F':
        q.popleft()
    else:
        q.pop()

print(' '.join(q))
### BUGGY CODE ###

H,W=[int(s) for s in input().split()]
M=80*(H+W)
inls=[[int(s) for s in input().split()] for _ in range(H)]
for i in range(H):
  x=[int(s) for s in input().split()]
  for j in range(W):
    inls[i][j]=abs(inls[i][j]-x[j])
dp=[[[0 for _ in range(M)] for _ in range(W)] for _ in range(H)]
dp[0][0][inls[0][0]]=1
for i in range(H):
  for j in range(W):
    x=inls[i][j]
    for k in range(M):
      if dp[i-1][j][k]==1:
        dp[i][j][k+x]=1
        dp[i][j][abs(k-x)]=1
      if dp[i][j-1][k]==1:
        dp[i][j][k+x]=1
        dp[i][j][abs(k-x)]=1
for k in range(M):
  if dp[i][j][k]==1:
    print(k)
    break


### FIXED CODE ###

import time
start = time.time()
H,W=[int(s) for s in input().split()]
inls=[[int(s) for s in input().split()] for _ in range(H)]
for i in range(H):
  x=[int(s) for s in input().split()]
  for j in range(W):
    inls[i][j]=abs(inls[i][j]-x[j])
dp=[[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(inls[0][0])
for i in range(H):
  for j in range(W):
    x=80*(H+W-i-j)
    for e in dp[i-1][j]:
      if e+inls[i][j]<x:
        dp[i][j].add(e+inls[i][j])
      dp[i][j].add(abs(e-inls[i][j]))
    for e in dp[i][j-1]:
      if e+inls[i][j]<x:
        dp[i][j].add(e+inls[i][j])
      dp[i][j].add(abs(e-inls[i][j]))
  if time.time() - start>1.7:
    dp[H-1][W-1].add(0)
    break
print(min(dp[H-1][W-1]))
### BUGGY CODE ###

S = list(input())


def f():
    cnt = 0
    pre = ''
    pre_idx = -1
    for i, s in enumerate(S):
        if not s: continue

        if pre and s != pre:
            cnt += 2
            S[i] = ''
            S[pre_idx] = ''
            pre = ''
        else:
            pre = s
            pre_idx = i
    return cnt


res = 0
while 1:
    tmp = f()
    if not tmp: break
    res += tmp

print(res)


### FIXED CODE ###

S = list(input())
stack = []

res = 0

for s in S:
    if stack and stack[-1] != s:
        stack.pop()
        res += 2
        continue
    stack.append(s)
print(res)
### BUGGY CODE ###

N = int(input())
S = input()
temp_min =10**15
for i in range(1,N):
    temp = S[0:i-1]
    temp2 = S[i:N]
    if temp_min > temp.count("W")+temp2.count("E"):
        temp_min = temp.count("W")+temp2.count("E")
print(temp_min)

### FIXED CODE ###

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

count_E = S[1:].count("E")
ans = count_E
for i in range(1,N):
    if S[i-1] == "W":
        count_E += 1
    if S[i] == "E":
        count_E -= 1
    if ans >count_E:
        ans = count_E
print(ans)
### BUGGY CODE ###

import copy
import math

N, K = list(map(int,input().split()))
As = list(map(int,input().split()))

sorted_As = sorted(As,reverse = True)
cut_As = copy.copy(sorted_As)
count_list = [0]*len(sorted_As)

'''
for i in range(K):
    index = cut_As.index(max(cut_As))
    count = count_list[index]
    count_list[index] += 1
    cut_As[index] = sorted_As[index] / (count+2)
'''

for i in range(K):
    count = count_list[0]
    count_list[0] += 1
    cut_As[0] = sorted_As[0] / (count+2)
    cut_As,sorted_As,count_list = (list(x) for x in zip(*sorted(zip(cut_As,sorted_As,count_list),reverse = True)))

print(math.ceil(max(cut_As)))


### FIXED CODE ###

def judge(As,K,C):
    count = 0
    for i in range(len(As)):
        if As[i]%C == 0:
            m = As[i]//C - 1
        else:
            m = As[i]//C
        count += m
    if count <= K:
        return True
    else:
        return False

N, K = list(map(int,input().split()))
As = list(map(int,input().split()))

l = 0
r = max(As)
while(r-l>1):
    mid = (l+r)//2
    if judge(As,K,mid):
        r = mid -1
    else:
        l = mid + 1
if judge(As,K,r):
    print(r)
else:
    print(r+1)
### BUGGY CODE ###

S = input()
T = input()
for i in range(len(T)):
    x = S[i]
    y = T[i]
    S = S.replace(x, 'X')
    S = S.replace(y, 'Y')
    S = S.replace('X', y)
    S = S.replace('Y', x)
if S == T:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
T = input()
N = len(S)
count = 0
R_1 = [-1 for i in range(26)]
R_2 = [-1 for i in range(26)]

answer = "Yes"
for i in range(N):
    r1 = ord(S[i]) - 97
    r2 = ord(T[i]) - 97
    if R_1[r1] >= 0:
        if r2 != R_1[r1]:
            answer = "No"
            break
    if R_2[r2] >= 0:
        if r1 != R_2[r2]:
            answer = "No"
            break
    if R_1[r1] < 0:
        R_1[r1] = r2
    if R_2[r2] < 0:
        R_2[r2] = r1
print(answer)
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N = i()
A = l()
L = []
L2 = []
for i in range(N):
    L.append(i+A[i]+1)
    L2.append(i-A[i]+1)
ans = 0
for l in L:
    c = L2.count(l)
    ans += c
print(ans)


### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N = i()
A = l()
L = []
L2 = [0]*(10**6)
for i in range(N):
    if i+A[i]+1 < 10**6:
        L.append(i+A[i]+1)
    if i-A[i]+1 >= 0 and i-A[i]+1 < 10**6:
        L2[i-A[i]+1] += 1
ans = 0
for l in L:
    ans += L2[l]
print(ans)
### BUGGY CODE ###

import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

d2 = {}
for k in range(N):
    a = A[k]

    if a not in d2:
        d2[a] = 0
        for i, n in d.items():
            if a == i:
                d2[a] += comb(n - 1, 2)
            else:
                d2[a] += comb(n, 2)
    print(d2[a])


### FIXED CODE ###

import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

b = 0
for n in d.values():
    b += comb(n, 2)

for k in range(N):
    a = A[k]
    print(b - d[a] + 1)
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a, int(b)-1) for a, b in ab]
    dct = {(a, b): i for i, (a, b) in enumerate(ab)}

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a == "B":
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    for i in range(n+1):
        dp1 = dp[i]
        if i < n:
            dp2 = dp[i+1]
            t = dct[("B", i)]
        for j in range(n+1):
            d = dp1[j]
            if i < n:
                dp2[j] = min(dp2[j], d+lb[t][i]+lw[t][j])
            if j < n:
                t2 = dct[("W", j)]
                dp1[j+1] = min(dp1[j+1], d+lb[t2][i]+lw[t2][j])
    print(dp[n][n])


main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a == "B", int(b)-1) for a, b in ab]
    dct_b = [0]*n
    dct_w = [0]*n
    for i, (a, b) in enumerate(ab):
        if a:
            dct_b[b] = i
        else:
            dct_w[b] = i

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a:
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    for i in range(n+1):
        dp1 = dp[i]
        if i < n:
            dp2 = dp[i+1]
            t = dct_b[i]
        for j in range(n+1):
            d = dp1[j]
            if i < n:
                dp2[j] = min(dp2[j], d+lb[t][i]+lw[t][j])
            if j < n:
                t2 = dct_w[j]
                dp1[j+1] = min(dp1[j+1], d+lb[t2][i]+lw[t2][j])
    print(dp[n][n])


main()
### BUGGY CODE ###

N = int(input())
A=[]

for i in range(N):
    S=input()
    if S in A:
        continue
    else:
        A.append(S)

print(len(A))

### FIXED CODE ###

N = int(input())
A=[]
 
for i in range(N):
    S=input()
    A.append(S)
 
print(len(list(set(A))))
### BUGGY CODE ###

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

test = [i for i in range(N) if P[i]==min(P[:i+1])]

print(len(test))


### FIXED CODE ###

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

dummy = 2*10**5
answer = 0

for p in P:
  if p <= dummy:
    answer += 1
    dummy = p

print(answer)
### BUGGY CODE ###

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

dp = [float('inf')] * n
dp[0] = 0;

for i in range(n - 1):
    distances = range(1, min(k + 1, n - i))
    for dis in distances:
        dp[i + dis] = min(dp[i + dis], dp[i] + abs(steps[i] - steps[i + dis]))

print(dp[n - 1])


### FIXED CODE ###

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

dp = [0] * n
dp[0] = 0;

for i in range(1, n):
    step_to = steps[i]
    dp[i] = min(
        [
            dp_from + abs(step_to - step_from)
            for dp_from, step_from in zip(
                dp[max(0, i - k):i], steps[max(0, i - k):i])
        ]
    )

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

#ABC074C
A, B, C, D, E, F=map(int, input().split())
A=100*A
B=100*B
count_A=F//A
count_B=F//B
count_C=F//C
count_D=F//D
max=0
ans=[0]*2
total=0
density=0
for i in range(count_A+1):
    for j in range(count_B+1):
        for k in range(count_C+1):
            for l in range(count_D+1):
                total=i*A+j*B+k*C+l*D
                if total!=0:
                    density=(k*C+l*D)/total
                    if total<=F and density<=E/(100+E) and max<=density:
                        max=density
                        ans[0]=total
                        ans[1]=k*C+l*D
                        if density==E/(100+E):
                            break
print(' '.join(map(str, ans)))


### FIXED CODE ###

#ABC074C
A, B, C, D, E, F=map(int, input().split())
A=100*A
B=100*B
count_A=F//A
count_B=F//B
count_C=F//C
count_D=F//D
max=-1
ans=[0]*2
total=0
density=0
for i in range(count_A+1):
    for j in range(count_B+1):
        if i*A+j*B<=F and 0<i*A+j*B:
            for k in range(count_C+1):
                if i*A+j*B+k*C<=F:
                    for l in range(count_D+1):
                        total=i*A+j*B+k*C+l*D
                        if total!=0:
                            density=(k*C+l*D)/total
                            if total<=F and density<=E/(100+E) and max<density:
                                max=density
                                ans[0]=total
                                ans[1]=k*C+l*D
                                if density==E/(100+E):
                                    print(' '.join(map(str, ans)))
                                    exit()
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n, k = map(int, input().split())
ll = 2*n // k
ans = 0
for i in range(1, ll+1):
    for j in range(1, ll+1):
        for m in range(1, ll+1):
            if ((m+i-j)*k) % 2 == 0 and ((i-m+j)*k) % 2 == 0 and ((m-i+j)*k) % 2 == 0:
                if (m+i-j) > 0 and (i-m+j) > 0 and (m-i+j) > 0:
                    if (m+i-j)*k//2 <= n and (i-m+j)*k//2 <= n and (m-i+j)*k//2 <= n:
                        ans += 1
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
ll = n // k
if ll % 2 == 0:
    l_odd = ll // 2
    l_even = ll // 2
else:
    l_odd = ll // 2 + 1
    l_even = ll // 2
if k % 2 == 0:
    ans = ll ** 3
    if n >= ll*k + k/2:
        ans += (ll+1)**3
    else:
        ans += ll**3
    print(ans)
else:
    print(ll ** 3)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    a.sort()
    for i in range(n):
        v = a[i]
        if dic[v] > 1:
            continue
        lim = v//2 + 1
        f = True
        for j in range(i):
            if a[j] > lim:
                break
            if a[i] % a[j] == 0:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import sqrt
from random import randint
def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main1():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    a.sort()
    for i in range(n):
        v = a[i]
        if dic[v] > 1:
            continue
        lim = v//2 + 1
        f = True
        for j in range(i):
            if a[j] > lim:
                break
            if a[i] % a[j] == 0:
                f = False
                break
        if f:
            ans += 1
    print(ans)

def main2():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    for v in a:
        if dic[v] > 1:
            continue
        tmp = Divisor_Set(v)
        tmp.remove(v)
        f = True
        for x in tmp:
            if x in dic:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    if randint(1, 2) == 1:
        main1()
    else:
        main2()
### BUGGY CODE ###

import random

def gcd(a,b):
        if b == 0:
                return a
        else:
                return gcd(b , a%b)

def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
 
a, b = map(int,input().split())
 
c = 1
m = gcd(a,b)
for i in range(1,m+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			c+=1
print(c)

### FIXED CODE ###

import random

def gcd(a,b):
        if b == 0:
                return a
        else:
                return gcd(b , a%b) 
def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

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

c = 1
m = gcd(a,b)

i = 1
while i * i <=m:
        if a%i == 0 and b%i == 0:
                if is_prime(i):
                        c+=1
                if is_prime(m//i):
                        c+=1
        i+=1
print(c)
### BUGGY CODE ###

import numpy as np
n,m = map(int,input().split())
a = []
b = []
for i in range(m):
    a_ , b_ = map(int,input().split())
    a.append(a_)
    b.append(b_)

broken_bridge = [0 for i in range(n-1)]
comp_task = [0 for i in range(m)]

a = np.array(a) - 1
b = np.array(b) - 1 
cnt = 0
conp_task = np.zeros(m)
in_task = np.zeros(m)

for i in range(n-1):
    if(np.any(a*np.logical_not(comp_task) == i )):
        in_task = (in_task+(a*np.logical_not(comp_task)==i)).astype(np.bool)
    if(np.any(b*np.logical_not(comp_task)*in_task == i+1)):
        cnt += 1
        comp_task = (comp_task + in_task).astype(np.bool)
        in_task = np.zeros(m)

print(cnt)



### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0

while(a.shape[0]):
    min_b = np.min(b)
    in_task = (a < min_b).astype(np.bool)
    cnt += 1
    tmp = np.logical_not(in_task)
    a = a[tmp]
    b = b[tmp]
    
print(cnt)