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

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

j = 1
temp = p_list[0]
for i in range(1,N):
  if p_list[i] > temp:
    continue
  sort_list = sorted(p_list[0:i+1])
  if p_list[i] <= sort_list[0]:
    j = j + 1
  else:
    temp = p_list[i]

print(j)

### FIXED CODE ###

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

j = 1
temp = p_list[0]
for i in range(1,N):
  if temp >= p_list[i]:
    j += 1
    temp = min(temp,p_list[i])

print(j)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = map(int, input().split())
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[(a, b)]=i
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i


    q = deque()
    seen = [False]*(N-1)
    used = [set() for _ in range(N)]
    q.append(top)
    while len(q)>0 and seen.count(False)>0:
        cur = q.popleft()
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                col = 1
                while col in used[cur] or col in used[i]:
                    col+=1
                seen[Edge[ed]] = col
                used[cur].add(col)
                used[i].add(col)
                q.append(i)

    print(K)
    print('\n'.join(map(str, seen)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = map(int, input().split())
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[(a, b)]=i
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i


    q = deque()
    seen = [False]*(N-1)
    used = [set() for _ in range(N)]
    q.append(top)
    while len(q)>0:
        cur = q.popleft()
        col = 1
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                while col in used[cur] or col in used[i]:
                    col+=1
                seen[Edge[ed]] = col
                used[cur].add(col)
                used[i].add(col)
                q.append(i)

    print(K)
    print('\n'.join(map(str, seen)))

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

from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    for x, y in xy:
        if x < x0 or x1 < x or y < y0 or y1 < y:
            continue
        count += 1
    return count

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(xsort[a][0], xsort[b][0], ysort[c][1], ysort[d][1]) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)

### FIXED CODE ###

from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ([xsort[i][0], ysort[j][1]] in xy)

def count_points_in_rec(x0, x1, y0, y1):
    point = cum[x1+1][y1+1] - cum[x0][y1+1] - cum[x1+1][y0] + cum[x0][y0]
    return point

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(a, b, c, d) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)
### BUGGY CODE ###


# import sys
# input = sys.stdin.readline
from collections import Counter


def main():
    s = input()
    t = input()
    ts = Counter(s)
    i = 0
    pos = 0

    while i < len(t):
        cur = pos % len(s)
        # print(len(t), i, cur, t[i], s[cur])

        if t[i] not in ts:
            pos = -1
            break

        if t[i] == s[cur]:
            i += 1
        # else:
        #     pos = -1
        #     break
        pos += 1

    print(pos)


if __name__ == '__main__':
    main()


### FIXED CODE ###


# import sys
# input = sys.stdin.readline
import bisect


def ch_to_int(c):
    return ord(c) - 96


def main():
    s = input()
    t = input()
    pos = 0
    count = 0
    ch = [[] for i in range(27)]

    for i in range(len(s)):
        ch[ch_to_int(s[i])].append(i)

    for i in range(len(t)):
        c = ch_to_int(t[i])
        li = ch[c]

        if len(li) == 0:
            pos = -1
            count = 0
            break

        next_index = bisect.bisect_left(li, pos)
        # print(next_index, pos, li)
        if next_index >= len(li):
            next_pos = li[0]
            count += 1
            pos = next_pos + 1
        else:
            if pos == li[next_index]:
                pos += 1
            else:
                pos = li[next_index] + 1
        # print(li, next_index, pos, count)

    print(pos + count * len(s))


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

b = input()
a = [i for i in b]
out = 0
for k in range(len(a)):
	for i in range(len(a) - 1):
		if a[i] == 'B' and a[i + 1] == 'W':
			out += 1
			a[i] = 'W'
			a[i + 1] = 'B'
		
print(out)

### FIXED CODE ###

b = input()
nes = []
nowb = 0
noww = 0
counter = 0
for i in b:
	if i == 'B':
		if noww == 0:
			nowb += 1
		else:
			counter += nowb * noww
			nowb += 1
			noww = 0
	else:
		if nowb != 0:
			noww += 1
		
counter += nowb * noww

print(counter)
### BUGGY CODE ###

import sys
import itertools

N, M, Q = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(Q)]

max_value = 0
#for A in itertools.permutations(range(1, M+1), N):
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp_value = 0
    for i in range(len(S)):
        if S[i][1] > len(A) or S[i][0] > len(A):
            continue

        if A[S[i][1] - 1] - A[S[i][0] - 1] == S[i][2]:
            tmp_value += S[i][3]
#            print(A, A[S[i][1] - 1], A[S[i][0] - 1], S[i][2], S[i])
    if tmp_value > max_value:
        max_value = tmp_value
print(max_value)

### FIXED CODE ###

import sys
import itertools

N, M, Q = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(Q)]

max_value = 0
#for A in itertools.permutations(range(1, M+1), N):
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp_value = 0
    for i in range(len(S)):
        if S[i][1] > len(A) or S[i][0] > len(A):
            continue

        if A[S[i][1] - 1] - A[S[i][0] - 1] == S[i][2]:
            tmp_value += S[i][3]
#            print(A, A[S[i][1] - 1], A[S[i][0] - 1], S[i][2], S[i])
    if tmp_value > max_value:
        max_value = tmp_value
print(max_value)
### BUGGY CODE ###

from math import ceil
import bisect
N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[a, ceil(b/A)] for a, b in L]
L = sorted(L, key=lambda x: x[0])
seen = 0
cnt = 0
while seen < N:
    target = L[seen]
    if target[1] <= 0:
        seen += 1
        continue
    ind_right_most = bisect.bisect_right([v[0] for v in L], target[0]+2*D)
    tmp = target[1]
    for i in range(seen, ind_right_most):
        L[i][1] -= tmp
    seen += 1
    cnt += tmp
print(cnt)


### FIXED CODE ###

from math import ceil
import bisect


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])

POS = [v[0] for v in L]
ES = [0]*(N+1)
ans, c = 0, 0
for i in range(N):
    c -= ES[i]
    if L[i][1] > c:
        t = L[i][1]-c
        ans += t
        c += t
        ES[bisect.bisect_right(POS, POS[i]+2*D)] += t
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
arr = list(map(int, input().split()))
big = 0
kitai = 0
for i in range(n-k+1):
    kitai = 0
    for j in range(i,i+k):
        kitai = kitai + (arr[j]+1)/2
    if big < kitai:
        big = kitai
print(big)

### FIXED CODE ###

n, k = map(int,input().split())
arr = list(map(int, input().split()))
kitai = 0
biglist = []
if k ==1:
    kitai = (max(arr)+1)/2
    print(kitai)
else:
    for i in range(n-k+1):
        if i == 0:
            big = 0
            for j in range(i+k):
                big = big + arr[j]
        else:
            big = biglist[i-1] - arr[i-1] + arr[i+k-1]
        biglist.append(big)
    max_value = max(biglist)
    max_index = biglist.index(max_value)
    for j in range(max_index,max_index+k):
        kitai = kitai + (arr[j]+1)/2
    print(kitai)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*n
for i in list(range(n))[1:]:
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in [max(0, i-ki-1) for ki in range(k)]])
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*n
for i in list(range(n))[1:]:
    tmp = max(0, i-k)
    dp[i] = min([dpk+abs(h[i]-hk) for dpk, hk in zip(dp[tmp:i], h[tmp:i])])
print(dp[-1])
### BUGGY CODE ###

n=int(input())
ans=set()
for i in range(n):
    ans=ans^set([input()])
print(len(ans))

### FIXED CODE ###

N=int(input())
s=set()
for i in range(N):s^={input()}
print(len(s))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val
    visited = set()
    def dfs(v):
        visited.add(v)
        changed_i, before_val = update_dp(v)
        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[changed_i] = before_val

    dfs(0)
    for a in ans:
        print(a)

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val

    visited = set()

    def dfs(v):
        visited.add(v)

        j = bisect.bisect_left(dp, A[v])
        before_val = dp[j]
        dp[j] = A[v]

        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[j] = before_val

    dfs(0)
    for a in ans:
        print(a)

main()
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
count = lambda x: a.count(x-1)+a.count(x)+a.count(x+1)
print(max(count(x) for x in range(min(a),max(a)+1)))

### FIXED CODE ###

cnt = [0]*10**5; input()
a = list(map(int,input().split()))
for x in a:cnt[x]+=1
print(max(sum(cnt[i:i+3])for i in range(min(a),max(a)+1)))
### BUGGY CODE ###

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

C = 1
#A_S = sorted(A, reverse=True)
#B_S = sorted(B, reverse=True)
A.sort(reverse=True)
B.sort(reverse=True)

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if C == 0:
            break
        if k in A and k in B:
            continue
        elif (k in A and k not in B):
            C *= len([x for x in B if x > k])
        elif (k not in A and k in B):
            C *= len([x for x in A if x > k])
        else:
            C *= (len([x for x in A if x > k]) *
                  len([x for x in B if x > k]) - (N*M-k))

print(C % (10**9+7))

### FIXED CODE ###

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

C = 1
A.sort(reverse=True)
B.sort(reverse=True)

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if aloop < N and bloop < M and k == A[aloop] and k == B[bloop]:
            aloop += 1
            bloop += 1
        elif aloop < N and k == A[aloop]:
            C *= bloop
            aloop += 1
        elif bloop < M and k == B[bloop]:
            C *= aloop
            bloop += 1
        else:
            C *= (aloop * bloop - (N * M - k))

        C = C % (10**9+7)
print(C)
### BUGGY CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
dp = [(0, 0)] * n
for j in range(k):
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        dp[i] = (l, r)
    imos = [0] * n
    for i in range(n):
        l, r = dp[i]
        imos[l] += 1
        if r < n - 1:
            imos[r + 1] -= 1
    tmp = 0
    for i in range(n):
        tmp += imos[i]
        a[i] = tmp
print(*a)


### FIXED CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
dp = [(0, 0)] * n
changed=set(range(n))
for j in range(k):
    for i in changed:
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        dp[i] = (l, r)
    imos = [0] * n
    for i in range(n):
        l, r = dp[i]
        imos[l] += 1
        if r < n - 1:
            imos[r + 1] -= 1
    tmp = 0
    for i in range(n):
        tmp += imos[i]
        a[i] = tmp
    if j>50:
        break
print(*a)
### BUGGY CODE ###

def ite(N, M):
    import itertools
    data = list(range(1, M+1, 1))
    return list(itertools.product(data, repeat=N))
  
def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

N, M, Q = list(map(int, input().split(" ")))
li = []
for i in range(Q):
    li.append(list(map(int, input().split(" "))))

m_s = 0
li2 = ite(N, M) 
for l2 in li2:
    if check(l2):
        s = score(l2, li)
        if m_s < s:
            m_s = s
            
print(m_s)

### FIXED CODE ###

def ite(N, M):
    import itertools
    return itertools.combinations_with_replacement(range(M),N)
def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

N, M, Q = list(map(int, input().split(" ")))
li = []
for i in range(Q):
    li.append(list(map(int, input().split(" "))))

m_s = 0
for l2 in ite(N, M):
    s = score(l2, li)
    if m_s < s:
      m_s = s
            
print(m_s)
### BUGGY CODE ###

n=int(input())
k=0
for i in range((n+1)//2):
    while (i+1)**2 < n:
        k+=1
print((k+1)**2)

### FIXED CODE ###

n=int(input())
print((int(n**0.5))**2)
### BUGGY CODE ###

N=int(input())
T=[]
A=[]
for i in range(N):
    t,a=map(int,input().split())
    T.append(t)
    A.append(a)

Tnow=T[0]
Anow=A[0]
ans=Tnow+Anow

for i in range(1,N):
    t=T[i]
    a=A[i]
    tempans=(t+a+ans-1)//(t+a)*(t+a)
    while True:
        tempT=tempans*t//(t+a)
        tempA=tempans*a//(t+a)
        if tempT>=Tnow and tempA>=Anow:
            ans=tempans
            Tnow=tempT
            Anow=tempA
            break
        else:
            tempans+=t+a
print(ans)



### FIXED CODE ###

N=int(input())
T=[]
A=[]
for i in range(N):
    t,a=map(int,input().split())
    T.append(t)
    A.append(a)

Tnow=T[0]
Anow=A[0]


for i in range(1,N):
    t=T[i]
    a=A[i]
    t1=(Tnow+t-1)//t*t
    a1=t1//t*a
    a2=(Anow+a-1)//a*a
    t2=a2//a*t
    if a1<Anow:
        Tnow=t2
        Anow=a2
    elif t2<Tnow:
        Tnow=t1
        Anow=a1
    elif t1+a1<=t2+a2:
        Tnow=t1
        Anow=a1
    else:
        Tnow=t2
        Anow=a2
print(Tnow+Anow)
### BUGGY CODE ###

from collections import Counter

N, M = map(int, input().split())
ans = [[] for _ in range(N)]
for _ in range(M):
    p, s = input().split()
    if 'AC' not in ans[int(p)-1]:
        ans[int(p)-1].append(s)

cnt = Counter(sum(ans, []))

print(cnt['AC'], cnt['WA'])


### FIXED CODE ###

import numpy as np

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

P = []
S = []

for _ in range(M):
    p, s = input().split()
    P.append(int(p))
    S.append(s)

AC = np.zeros(N)
WA = np.zeros(N)

for i in range(M):
    if AC[P[i]-1] == 0:
        if S[i] == 'WA':
            WA[P[i]-1] += 1
        else:
            AC[P[i]-1] += 1

WA[AC == 0] = 0

print(int(sum(AC)), int(sum(WA)))
### BUGGY CODE ###

import itertools

N = int(input())
s_list = []
out = 0

for i in range(N):
  s_list.append(''.join(sorted(list(input()))))
  
for s1, s2 in itertools.combinations(s_list, r=2): 
	out = out+1 if s1==s2 else out
    
print(out)

### FIXED CODE ###

N = int(input())
s_list = {}
out = 0

for i in range(N):
	s_in =''.join(sorted(list(input())))
	if s_in in s_list:
		s_list[s_in]+=1
	else:
		s_list[s_in]=1
    
for val in s_list.values():
  out += int(val*(val-1)/2)
    
print(out)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(x) - 1 for x in input().split()]
now = 0
b = [0] * n
while k!= 0:
    if k & 1:
        now = a[now]
    k >>= 1
    for i in range(n):
        b[i] = a[a[i]]
    a = b[:]
print(now+1)

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]
lis = [None] * n
now = 0
lis[0] = 0
num = 0
rode = [0]
while True:
    now = a[now]
    num += 1
    rode.append(now)
    if num == k:
        print(now + 1)
        break
    if lis[now] == None:
        lis[now] = num
    else:
        print(rode[lis[now] + (k-lis[now]) % (num - lis[now])] + 1)
        break
### BUGGY CODE ###

import numpy as np


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = np.zeros((city_count + 1, city_count + 1), np.int_)

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l, r] += 1

    city_list.cumsum(1, out=city_list)

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(city_list[p:q + 1, q].sum())


if __name__ == '__main__':
    main()


### FIXED CODE ###

from array import array
from itertools import accumulate, repeat, starmap
from operator import add, itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for city_index in range(2, city_count + 1):
        city_list[city_index] = array('L', starmap(
            add, zip(*(city_list[city_index + i] for i in (-1, 0)))))

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(city_list[q][q] - city_list[p - 1][q])


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

def func():
    N, W = map(int, input().split())
    w = [0]*N
    v = [0]*N

    for i in range(N):
        w[i], v[i] = map(int, input().split())

    dp = [[0]*(W+1) for i in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            if j >= w[i]:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
            else:
                dp[i+1][j] = dp[i][j]


    print(dp[N][W])

func()

### FIXED CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = set(table)
    return table


def common_divisor(x, y):
    xd = divisor(x)
    yd = divisor(y)
    return xd & yd


a, b = map(int, input().split())
cd = sorted(list(common_divisor(a, b)))

cnt = 1
div = {1}
for i in cd[1:]:
    i_d = divisor(i)
    if len(div & i_d) == 1:
        cnt += 1
    div |= i_d

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = set(table)
    return table


def common_divisor(x, y):
    xd = divisor(x)
    yd = divisor(y)
    return xd & yd


a, b = map(int, input().split())
cd = sorted(list(common_divisor(a, b)))

cnt = 1
div = {1}
for i in cd[1:]:
    i_d = divisor(i)
    if len(div & i_d) == 1:
        cnt += 1
    div |= i_d

print(cnt)