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

def main():
    n, w_max = map(int, input().split())
    dp = [[0] * (w_max + 1) for _ in range(n + 1)]
    for i1 in range(1, n + 1):
        w, v = map(int, input().split())
        for col in range(1, w_max + 1):
            if w <= col:
                dp[i1][col] = max(dp[i1 - 1][col], dp[i1 - 1][col - w] + v)
            else:
                dp[i1][col] = dp[i1 - 1][col]

    print(dp[-1][-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

n, w = map(int, input().split())
things = []
things.append([0,0])
things += [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

def do_dp():
  for i,thing in enumerate(things):
    dp_1 = dp[i-1]
    for j in range(1, w + 1):      
      dp[i][j] = dp_1[j-thing[0]] + thing[1]  if (j - thing[0]) >= 0 else dp_1[j]
      dp[i][j] = max(dp[i][j], dp_1[j])

do_dp()
print(dp[n][w])
### BUGGY CODE ###

N =int(input())
L =[]
for i in range(N):
    S = input()
    if not S in L:
        L.append(S)
print(len(L))

### FIXED CODE ###

N =int(input())
S = [input() for i in range(N)]
ans = len(set(S))
print(ans)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
tmp_m = 1
for i in range(K):
    tmp_m = tmp_m * A[i]
for i in range(K, N):
    tmp_m_old = tmp_m
    tmp_m = (tmp_m / A[i - K]) * A[i]
    if tmp_m_old < tmp_m:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
for i in range(K, N):
    if A[i] > A[i - K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = input()
a = input().split()

result = []

for i in range(len(a)):
    result.append(a.index(str(i + 1)) + 1)

print(*result)


### FIXED CODE ###

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

ans = [0] * n

for i in range(n):
    ans[a[i] - 1] = i + 1

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

import numpy as np

s = input()

a = np.zeros(len(s)+1, dtype='i8')
res = 0
for i in range(len(s)):
    for k in range(i+4, len(s)+1):
        if int(s[i:k]) % 2019 == 0:
            res += a[i] + 1
            a[k] += 1
            break

print(res)


### FIXED CODE ###

s = input()[::-1]

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + (10 * p) * int(s[i])) % 2019
    cnt[now] = cnt.get(now, 0) + 1
    p = (p * 10) % 2019

print(sum(cnt[k] * (cnt[k] - 1) // 2 for k in cnt))
### BUGGY CODE ###

n=int(input())
b=[]
for i in range(n):
    a=input()
    if a not in b:
        b.append(a)
print(len(b))

### FIXED CODE ###

n=int(input())
b={}
for i in range(n):
    a=input()
    b[a]=1
print(len(b))
### BUGGY CODE ###

n = int(input())
ls = []
count = 0
for x in range(n):
    ls.append(input())
li2 = []
for i in ls:
    if i not in li2:
        li2.append(i)
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
ls = []
count = 0
for x in range(n):
    ls.append(input())
ls = set(ls)
print(len(ls))
### BUGGY CODE ###

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

l = [i for i in range(a, b + 1) if i % x == 0]
print(len(l))


### FIXED CODE ###

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

print((b // x) - ((a - 1) // x))
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]) and answer > (x2-x1) * (y2-y1):
                        answer = (x2-x1) * (y2-y1)

    print(answer)


### FIXED CODE ###

import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]) and answer > (x2-x1) * (y2-y1):
                        answer = (x2-x1) * (y2-y1)

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

import sys


n, x, y = map(int, sys.stdin.readline().split())
dist = []
for i in range(n):
    dist.append([])
    for j in range(n):
        dist[i].append(abs(j - i))

dist[x-1][y-1] = 1
dist[y-1][x-1] = 1

for k in range(n):
    for j in range(n):
        for i in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        final[dist[i][j]-1] += 1

for one in final:
    print(one)

### FIXED CODE ###

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))
### BUGGY CODE ###

from itertools import product
N = int(input())
s = [int(input()) for _ in range(N)]
a = list(product(range(2),repeat = N))
s.sort(reverse=True)
while len(s) >0 and sum(s)%10==0:
  s.pop()
print(sum(s))

### FIXED CODE ###

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

if sum(s)%10 != 0:
  print(sum(s))
else:
  for i in range(N):
    if s[i] %10 != 0:
      print(sum(s)-s[i])
      exit()
  print(0)
### BUGGY CODE ###

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

count = 0
for i in range(0, N):
    for j in range(i + A[i], N):
        if abs(i - j) == A[i] + A[j]:
            count += 1

print(count)

### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))
AI = tuple(i + a for i, a in enumerate(A))
AJ = tuple(i - a for i, a in enumerate(A))

cai = {}
caj = {}
vali = set()
valj = set()
for ai, aj in zip(AI, AJ):
    if not ai in cai:
        cai[ai] = 0
    if not aj in caj:
        caj[aj] = 0

    cai[ai] += 1
    vali.add(ai)

    caj[aj] += 1
    valj.add(aj)

count = 0
for val in vali & valj:
    count += cai[val] * caj[val]

print(count)
### BUGGY CODE ###

import math
import sys
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


x, y = map(int, input().split())
if x  > 2 * y:
    print("0")
    sys.exit()
elif y  > 2 * x:
    print("0")
    sys.exit()
elif (x + y) % 3 != 0:
    print("0")
    sys.exit()


z = x + y
a = z / 3
n = a
b = 2 * a
r = 0
while (True):
    if a == x and b == y:
        break
    a += 1
    b -= 1
    r += 1
    
print(combinations_count(n, r) % (10 ** 9 + 7))
    
        



        


    







        



### FIXED CODE ###

import math
import sys
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10 ** 9 + 7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

    
x, y = map(int, input().split())
if x  > 2 * y:
    print("0")
    sys.exit()
elif y  > 2 * x:
    print("0")
    sys.exit()
elif (x + y) % 3 != 0:
    print("0")
    sys.exit()


z = x + y
a = int(z / 3)
n = a
b = 2 * a
r = 0
ans = 1
while (True):
    if a == x and b == y:
        break
    a += 1
    b -= 1
    r += 1



print(cmb(n, r, mod))
### BUGGY CODE ###

n=int(input())
a_dict={}
for i in range(n):
    a=input()
    if a not in a_dict:
        a_dict[a]=0
    else:
        a_dict[a]+=1
moji=[i for i,j in a_dict.items() if j==max(a_dict.values()) ]
moji=sorted(moji)
for i in moji:
    print(i)

### FIXED CODE ###

n=int(input())
a_dict={}
for i in range(n):
    a=input()
    if a not in a_dict:
        a_dict[a]=0
    else:
        a_dict[a]+=1
# moji=[i for i,j in a_dict.items() if j==max(a_dict.values()) ]
moji=[]
j=max(a_dict.values())
for i,k in a_dict.items():
    if k==j:
        moji.append(i)
moji=sorted(moji)
for i in moji:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
lis = []
N = int(input().rstrip())
for i in range(N):
  str = input().rstrip()
  counter = {}
  for c in str:
    if not c in counter:
        counter[c] = 1
    else:
        counter[c] += 1
  lis.append(counter)
count = 0
for i in range(N):
  for j in range(i+1, N):
    if lis[i] == lis[j]:
      count += 1
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
lis = {}
counter = 0
N = int(input().rstrip())
for i in range(N):
  str = "".join(sorted(list(input().rstrip())))
  if str in lis:
    lis[str] += 1
    counter += lis[str]
  else:
    lis[str] = 0
print(counter)
### BUGGY CODE ###

n,k = map(int,input().split())
h=sorted(list(int(input()) for i in range(n)))
h+=h
mi=float('inf')
a=0
for i in range(int(len(h)/2)):
    tmp=h[i:i+k]
    if mi > max(tmp)-min(tmp):
        mi=max(tmp)-min(tmp)
        a=i

print(max(h[a:a+k])-min(h[a:a+k]))

### FIXED CODE ###

n,k = map(int,input().split())
h=list(int(input()) for i in range(n))
h.sort()
mi=float('inf')

for i in range(n-k+1):
    mi = min(mi, h[i+k-1]-h[i])
 
print(mi)
### BUGGY CODE ###

n=int(input())
*a,=map(int,input().split())

b=[0]

for i in range(n):
  b.append(a[i]+b[i])

L={}
for i in range(n+1):
      if b[i] in b:
            if b[i] in L:
                  L[b[i]]+=1
            else:
                  L[b[i]]=1
ans=0
for i in L.values():
      if i>1:
            ans+=i*(i-1)//2
print(ans)         

### FIXED CODE ###

import collections

n=int(input())
*a,=map(int,input().split())
 
b=[0]
 
for i in range(n):
  b.append(a[i]+b[i])
 
L=collections.Counter(b)

ans=0
for i in L.values():
      if i>1:
            ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))

#numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
#zeros = [[0] * w for i in range(h)]


R,G,B,N = map(int, stdin.readline().rstrip().split())
ans = 0
for r in range(N//R+1):
    for g in range((N-(r*R))//G + 1):
        b = (N - R*r - G*g) / B
        if b%1==0 and b>=0:
            ans += 1
print(ans)


### FIXED CODE ###

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))

#numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
#zeros = [[0] * w for i in range(h)]


def main():
    R,G,B,N = map(int, stdin.readline().rstrip().split())
    ans = 0
    for r in range(N//R+1):
        for g in range((N-(r*R))//G + 1):
            b = (N - R*r - G*g) / B
            if b%1==0 and b>=0:
                ans += 1
    print(ans)

main()
### BUGGY CODE ###

while 1:
    try:
        count=0;
        x=int(input())
        if x==1:
            print(0)
        elif x==2:
            print(1)
        else:
            a=[int(i) for i in range(2,x+1)]
            for i in  range(len(a)):
                count1=0
                for j in range(2,a[i]):
                    if a[i]%j==0:
                        count1+=1
                if count1==0:
                    count+=1
            print(count)        
    except EOFError:
        break

### FIXED CODE ###

str1=[0 for i in range(10**6)]
str1[0]=1
str1[1]=1
for i in range(2,(10**6)):
    if str1[i]==0:
        for j in range(2,(10**6)):
            if i*j>=len(str1):
                break
            else:
                str1[i*j]=1
            
while 1 :
    try:
        x=int(input())
        count=0
        for i in range(1,x+1):
            if str1[i]==0:
                count+=1
        print(count)
        
    except EOFError:
        break
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*M
C = [0]*M
for i in range(M):
    B[i], C[i] = map(int, input().split())

A.sort()

for i in range(M):
    id = bisect.bisect_left(A, C[i])
    if id >= B[i]:
        A[:id] = A[B[i]:id]+[C[i]]*B[i]
    else:
        A[:id] = [C[i]]*id

print(sum(A))


### FIXED CODE ###

import collections
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*M
C = [0]*M
table = collections.defaultdict(int)
for x in A:
    table[x] += 1
for i in range(M):
    B[i], C[i] = map(int, input().split())
    table[C[i]] += B[i]

count = N
ans = 0
table = list(table.items())
table.sort(key=lambda x: x[0], reverse=True)
for x in table:
    if count > x[1]:
        count -= x[1]
        ans += x[0]*x[1]
    else:
        ans += x[0]*count
        break

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

n,m=map(int,input().split())
flag=False
one = []
enu = []
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    one.append(b)
  elif b==n:
    enu.append(a)

for i in one:
  if i in enu:
    flag=True
    break

if flag: print('POSSIBLE')
else: print('IMPOSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
li = []
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    li.append(b)
  elif b==n:
    li.append(a)

if len(set(li))==len(li): print('IMPOSSIBLE')
else: print('POSSIBLE')
### BUGGY CODE ###

import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

get_primes(10**2)

for p in get_primes(C):
  if C % p == 0:
    pfac.append(p)
    while C % p == 0:
      C //= p
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)

### FIXED CODE ###

import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, 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]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)
### BUGGY CODE ###

from numba import njit, i8
import numpy as np

def main():
    mod = 10**9+7
    k = int(input())
    n = len(input())

    @njit(i8[:](i8, i8), cache=True)
    def num_calc(n, mod):
        fact = np.ones(n+1, dtype=np.int64)
        for i in range(2, n+1):
            fact[i] = fact[i-1]*i % mod
        return fact

    @njit(i8[:](i8, i8), cache=True)
    def num_calc2(k, mod):
        power = np.ones(k+1, dtype=np.int64)
        for i in range(1, k+1):
            power[i] = power[i-1]*25 % mod
        return power

    fact = num_calc(n+k, mod).tolist()
    power = num_calc2(k, mod).tolist()
    nk = fact[n+k]

    print(sum([pow(fact[n+k-i]*fact[i] % mod, mod-2, mod)
               * nk*power[i] % mod for i in range(k+1)]) % mod)


main()


### FIXED CODE ###

def main():
    mod = 10**9+7
    k = int(input())
    s = input()
    n = len(s)
    fact = [1, 1]
    for i in range(2, 2*(10**6)+1):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

    ans = 0
    for i in range(k+1):
        ans = (ans+nCr(n+k, i)*pow(25, i, mod)) % mod
    print(ans)


main()
### BUGGY CODE ###

import heapq

n, m = [int(v) for v in input().split(' ')]

links = []
for i in range(n):
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1
    links[r].append((l, c))

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n0 + 1))

print("-1")

### FIXED CODE ###

import heapq

n, m = [int(v) for v in input().split(' ')]

links = []
for i in range(n):
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1
    links[r].append((l, c))

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if (closed & (1 << n0)) != 0:
        continue
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n2))

print("-1")
### BUGGY CODE ###

over = 10**18

n = int(input())
a = list(map(int, input().split()))
ans = 1;

for i in range(n):
  if a[i] == 0:
    ans = 0
if not ans == 0:
  for i in range(n):
    ans = ans * a[i]
    if ans > over:
      ans = -1
if ans < 0:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

over = 10**18

n = int(input())
a = list(map(int, input().split()))
ans = 1;

for i in range(n):
  if a[i] == 0:
    ans = 0
if not ans == 0:
  for i in range(n):
    ans = ans * a[i]
    if ans > over:
      ans = -1
      break
if ans < 0:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        visited[u] = True
        for v in edges[u]:
            if visited[v]:
                continue
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
        max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

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

ans = [0] * (n - 1)


def col(now, color):
    c = 1
    for (b, j) in A[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b, c)
        c += 1


col(0, 0)
print(max(ans))
for a in ans:
    print(a)
### BUGGY CODE ###

import math
A,B = map(int,input().split())
N = max(A,B)
prime = []

tA = A
tB = B
for i in range(2, math.ceil(N**0.5)+1):
    if tA%i==0 and tB%i==0:
        while tA%i==0:
            tA //= i
        while tB%i==0:
            tB //= i
        prime.append(i)

if tA!=1 or tB != 1:
    N = max(tA,tB)
    for i in range(2, N+1):
        if tA%i==0 and tB%i==0:
            while tA%i==0:
                tA //= i
            while tB%i==0:
                tB //= i
            prime.append(i)

# print(prime)
print(len(prime)+1)

### FIXED CODE ###

import math
A,B = map(int,input().split())
N = max(A,B)
prime = []

tA = A
tB = B
for i in range(2, math.ceil(N**0.5)+1):
    Aflag = False
    Bflag = False
    if tA%i==0:
        Aflag = True
        while tA%i==0:
            tA //= i
    if tB%i==0:
        Bflag = True
        while tB%i==0:
            tB //= i
    if Aflag == True and Bflag == True:
        prime.append(i)

if tA!=1 and tA == tB:
    prime.append(tA)

# print(prime)
print(len(prime)+1)
### BUGGY CODE ###

#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
d=defaultdict(int)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    m=n-set(y)
    for i in m:
        n.remove(i)
        for j in range(M):
            if i==x[j]:
                if d[y[j]]<=d[i]:
                    d[y[j]]=d[i]+1
                y[j]=0
print(max(d.values()))

### FIXED CODE ###

from collections import defaultdict, deque

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

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
l = []

for i in range(1, n + 1):
    cnt = 0
    for j in range(n - 1):
        if i == a[j]:
            cnt += 1
    l.append(cnt)
            
for k in range(n):
    print(l[k])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [0] * n

for i in a:
    l[i - 1] += 1
    
for k in range(n):
    print(l[k])
### BUGGY CODE ###

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

ans=0
for _ in range(2*(10**4)):
    count=0
    for i in range(n):
        if a[i]%2!=0:
            a[i]*=3
            count+=1
        else:
            a[i]=a[i]//2
            break
    if count==n:
        break
    if count!=n:
        ans+=1
print(ans)

### FIXED CODE ###

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

b=[]
for i in range(1,30):
    b.append(2**i)
#print(b)
ans=0
u=len(b)
for i in range(n):
    for j in range(u):
        if a[i]%b[j]==0:
            ans+=1
print(ans)