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

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

#from math import gcd
from fractions import gcd

def get_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: # NNが平方数のときに√Nを2個出力しないようにする
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def get_primes(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
        primes.difference_update(range(i*2, n+1, i))
    primes = list(primes)
    
    return primes

g = gcd(a,b)
primes = get_primes(g)
ans = 1 # 1は素数ではないが答えには入る

for p in primes:
    if g % p == 0:
        ans += 1
        
print(ans)

### FIXED CODE ###

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

#from math import gcd
from fractions import gcd

g = gcd(a,b)

pf = {}

for i in range(2,int(g**0.5)+1):
    while g % i == 0:
        pf[i] = pf.get(i,0) + 1
        g //= i
if g > 1: pf[g] = 1

ans = 1 + len(pf.keys()) # 1は素数ではないが答えには入る

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

N,K=map(int,input().split())
S=input()+"2"
if S[0]=="1":
    _list=[]
else:
    _list=[0]
cnt=1
for i in range(N):
    if S[i]==S[i+1]:
        cnt+=1
    else:
        _list.append(cnt)
        cnt=1
C=len(_list)
K=min(C,K)
print(max([sum(_list[2*i:2*i+2*K+1]) for i in range(C-K+1)]))

### FIXED CODE ###

N,K = list(map(int,input().split()))
S = [int(i) for i in list(input())]
S.append(2)

S2 = []
cnt = 1
for i in range(N):
    if S[i] != S[i+1]:
        S2.append([S[i],cnt])
        cnt = 1
    else:
        cnt += 1

if S2[0][0] == 0:
    S2 = [[1,0]] + S2
if S2[-1][0] == 0:
    S2.append([1,0])    
    
SUM = [0]
for i in range(len(S2)):
    SUM.append(SUM[i] + S2[i][1])
T = []
for i in range(0,max(1,len(SUM)//2-K),1):
    T.append(SUM[min(len(SUM)-1,2*(K+i)+1)]-SUM[2*i])
print(max(T))
### BUGGY CODE ###

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

dp = [0]*N

for i in range(N-1):
    if i >= K:
        x = dp[i]+abs(h[i+1]-h[i])
        for j in range(1,K):
            x = min(x,dp[i-j]+abs(h[i+1]-h[i-j]))
            
    else:
        x = dp[i]+abs(h[i+1]-h[i])
        for j in range(1,i+1):
            x = min(x,dp[i-j]+abs(h[i+1]-h[i-j]))
    
    dp[i+1] = x            



print(dp[-1])

### FIXED CODE ###

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

dp = [0]*N

for i in range(N-1):
    if i >= K:
        x = dp[i]+abs(h[i+1]-h[i])
        for j in range(1,K):
            x = min(x,dp[i-j]+abs(h[i+1]-h[i-j]))
            
    else:
        x = dp[i]+abs(h[i+1]-h[i])
        for j in range(1,i+1):
            x = min(x,dp[i-j]+abs(h[i+1]-h[i-j]))
    
    dp[i+1] = x            



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

'''
参考
https://qiita.com/c-yan/items/f7c99c8f8ec418a58c42

棒の全長をL、切断箇所をCとすると、かかるコストは|2C-L|となる
（左端から切断箇所までの長さを2倍し、元の棒の全長を引いたものの絶対値）
∵
・CがL/2よりも左にある場合（=棒の左端からCまでの長さのほうが短い）
⇒Cよりも左側に2C-L足すか、右側を2C-L減らす
・CがL/2よりも右にある場合（=棒の左端からCまでの長さのほうが長い）
⇒Cよりも左側を2C-L減らすか、右側に2C-L足す

与えられたリストAのうち、どの地点をCとするかは
リストAの先頭の要素からN-1個の要素をそれぞれ調べ、
先頭要素から現在の要素までの合計（累積和）を格納するリストを別途作成、
そのリストに対して|2C-L|が最小となるケースを調べる
'''
N = int(input())
A = list(map(int, input().split()))
L = sum(A)
tmp = []

for i in range(N):
    tmp.append(sum(A[:i+1]))

cost = min(abs(c*2-L) for c in tmp)
print(cost)


### FIXED CODE ###

'''
参考
https://qiita.com/c-yan/items/f7c99c8f8ec418a58c42

棒の全長をL、切断箇所をCとすると、かかるコストは|2C-L|となる
（左端から切断箇所までの長さを2倍し、元の棒の全長を引いたものの絶対値）
∵
・CがL/2よりも左にある場合（=棒の左端からCまでの長さのほうが短い）
⇒Cよりも左側に2C-L足すか、右側を2C-L減らす
・CがL/2よりも右にある場合（=棒の左端からCまでの長さのほうが長い）
⇒Cよりも左側を2C-L減らすか、右側に2C-L足す

与えられたリストAのうち、どの地点をCとするかは
リストAの先頭の要素からN-1個の要素をそれぞれ調べ、
先頭要素から現在の要素までの合計（累積和）を格納するリストを別途作成、
そのリストに対して|2C-L|が最小となるケースを調べる
'''
N = int(input())
A = list(map(int, input().split()))
L = sum(A)
#tmp = []
tmp = A[:-1]

for i in range(1, N-1):
#    tmp.append(sum(A[:i+1]))       # 実行時間超過してしまうためコメントアウト
    tmp[i] += tmp[i-1]

cost = min(abs(c*2-L) for c in tmp)
print(cost)
### BUGGY CODE ###

import itertools
K,S=map(int,raw_input().split())
l=list( itertools.product(range(K+1), repeat=3 ) )

cnt=0
for i,j,k in l:
	if i+j+k==S:
		cnt+=1
print cnt


### FIXED CODE ###

K,S=map(int,raw_input().split())

cnt=0
for x in range(K+1):
	for y in range(K+1):
		z=S-x-y
		if z>=0 and z<=K:
			cnt+=1
print cnt
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)

buf = []
for i in range(x):
    for j in range(y):
        buf.append(a[i]+b[j])

buf = sorted(buf,reverse=True)[:k]
ans = []

for i in buf:
    for j in range(z):
        ans.append(i+c[j])

ans = sorted(ans,reverse=True)
[print(ans[i]) for i in range(k)]


### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)

buf = []
for i in range(x):
    for j in range(y):
        buf.append(a[i]+b[j])

buf = sorted(buf,reverse=True)[:k]
ans = []

for i in buf:
    for j in range(z):
        ans.append(i+c[j])

ans = sorted(ans,reverse=True)
[print(ans[i]) for i in range(k)]
### BUGGY CODE ###

T = int(input())

for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()

    if S[-1] == '1':
        print('1')

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        tmp = set()
        if S[j] == '0':
            for v in win:
                tmp.add(v ^ A[j])
            win |= tmp
        else:
            for v in win:
                if v ^ A[j] not in win:
                    tmp.add(v)
            win -= tmp

    if 0 in win:
        print('0')
    else:
        print('1')


### FIXED CODE ###

T = int(input())

for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        base = A[j]
        for v in win:
            base = min(base, base ^ v)

        if S[j] == '0':
            win.add(base)
        else:
            if base:
                print('1')
                break
    else:
        print('0')
### BUGGY CODE ###

n,k=map(int,input().split())
x,y,xy=[],[],[]
for _ in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
  xy.append((a,b))
x.sort()
y.sort()
ans=float('inf')
for i in range(n-1):
  x1=x[i]
  for j in range(i+1,n):
    x2=x[j]
    for l in range(n-1):
      y1=y[l]
      for m in range(l+1,n):
        y2=y[m]
        cnt=0
        for o in range(n):
          x3,y3=xy[o]
          if x1<=x3<=x2 and y1<=y3<=y2:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(x2-x1)*(y2-y1))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
x,y,xy=[],[],[]
for _ in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
  xy.append((a,b))
x.sort()
y.sort()
ans=float('inf')
for i in range(n-1):
  x1=x[i]
  for j in range(i+1,n):
    x2=x[j]
    for l in range(n-1):
      y1=y[l]
      for m in range(l+1,n):
        y2=y[m]
        cnt=0
        for o in range(n):
          x3,y3=xy[o]
          if x1<=x3<=x2 and y1<=y3<=y2:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(x2-x1)*(y2-y1))
print(ans)
### BUGGY CODE ###

N,M,Q=map(int, input().split())
matrix=[]

for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
    
import itertools
scorelist=[]
k = itertools.product(range(1,M+1), repeat=N)
for i in k:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    scorelist.append(score)
print(max(scorelist))

### FIXED CODE ###

from itertools import combinations_with_replacement
N,M,Q = map(int,input().split())
A = []
for i in range(Q):
    b = list(map(int,input().split()))
    A.append(b)

T = range(1,M+1)
K = list(combinations_with_replacement(T,N))

ans = 0
for line in K:
    total = 0
    for combi in A:
        if line[combi[1]-1] - line[combi[0]-1] == combi[2]:
            total += combi[3]
    ans = max(total,ans)

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

import re

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

answer = []
pattern = re.compile(r'AC')

length = len

for _ in range(q):
    l, r = map(int, input().split()) 
    answer.append(length(re.findall(pattern, s[l-1:r])))

for ans in answer:
    print(ans)


### FIXED CODE ###

import re

n, q = map(int, input().split())
s = input()
count = [0] * len(s)
for ind, char in enumerate(s[1:], 1):
    if char == 'C' and s[ind-1] == 'A':
        count[ind] = count[ind-1] + 1
    else:
        count[ind] = count[ind-1]

# print(count)
answer = []

for _ in range(q):
    l, r = map(int, input().split()) 
    answer.append(count[r-1] - count[l-1])

for ans in answer:
    print(ans)
### BUGGY CODE ###

# coding: utf-8
H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        for k in range(i, min(H+1, i+a)):
            if k - a >= 0:
                dp[k] = min(dp[k], dp[i-1] + b)
            else:
                dp[k] = min(dp[k], b)
    # print(*dp)
print(dp[H])

### FIXED CODE ###

# coding: utf-8
H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
top = 10**9
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    # print(*dp)
print(dp[H])
### BUGGY CODE ###

a,b,n = map(int,input().split())
sum = 0
ans = 0

for i in range(1,n+1):
   sum += (a*i)//b-a*(i//b)
   ans = max(sum,ans)
   sum = 0 
    
print(ans)

### FIXED CODE ###

A, B, N = map(int, input().split())
ans = 0
x = min(B-1, N)
print((A*x)//B-A*(x//B))
### BUGGY CODE ###

N = int(input())

# 約数の全列挙
def divisors(n):
    for i in range(int(n**0.5)+1, 0, -1):
        if n % i == 0:
            return i
    return 1

start = divisors(N)

print('0 0 0 {} {} 0'.format(start, N // start))

### FIXED CODE ###

S = int(input())
MOD = 10**9

y2 = -(-S // 10**9)
x2 = -(S - y2 * (10**9))

print('0 0 {} 1 {} {}'.format(MOD, x2, y2))
### BUGGY CODE ###

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

sm=0

for i in range(n-1):
  for j in range(i+1,n):
    b=a[i]*a[j]
    sm+=b
    sm=sm%((10**9)+7)

print(sm)


### FIXED CODE ###

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

sm=0
sumj=sum(a)

for i in range(n-1):
  sumj-=a[i]
  sm+=sumj*a[i]


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

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

ans = False
for i in l1:
    if i in ln:
        ans = True
        break
if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
l1 = []
ln = []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l1.append(b)
    elif b == 1:
        l1.append(a)
    elif a == n:
        ln.append(b)
    elif b == n:
        ln.append(a)
l1.sort()
ln.sort()
ans = False
for i in l1:
    low = 0
    high = len(ln) - 1
    while low <= high:
        mid = (low + high)//2
        if ln[mid] == i:
            ans = True
            break
        elif ln[mid] > i:
            high = mid - 1
        else:
            low = mid + 1
    if ans:
        break
if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

h=0
a=list(input())
for i in range(1,len(a)):
  r=int(a[i])
  if int(a[i-1])==r:
    if r==0:
      b=1
    else:
      b=0
    a.pop(i)
    a.insert(i,b)
    h+=1
print(h)

### FIXED CODE ###

a = list(input())
s = a[0]
count = 0
if s == "0":
    for i in range(1, len(a)):
        if int(a[i]) != i % 2:
            count += 1
elif s == "1":
    for i in range(1, len(a)):
        if int(a[i]) != (i + 1) % 2:
            count += 1
print(count)
### BUGGY CODE ###


md=10**9+7
t=1
# t=int(input())

for some_num in range(0,t):
    n=int(input())
    vals=[int(i) for i in input().split(" ")]

    sum=0

    for i in range(0,n-2):
        ts=0
        for j in range(i+1,n):
            ts+=(vals[j])

        sum=(sum+ ts*vals[i])% md

    sum=(vals[n-1]*vals[n-2] + sum )%md


print(sum)



### FIXED CODE ###


md=10**9+7
t=1
# t=int(input())

for some_num in range(0,t):
    n=int(input())
    vals=[int(i) for i in input().split(" ")]

    s=0
    for i in range(0,n):
        s=(s+vals[i])%md

    csum=0

    for i in range(0,n-1):
        s-=vals[i]

        csum= (csum+vals[i]*s)%md

    print(csum)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    S = input()
    Q = int(input())
    qs = list(input() for _ in range(Q))
    rev = False
    for q in qs:
        q = q.split()
        if q[0] == '1':
            rev = not(rev)
        else:
            if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
                S = q[2] + S
            else:
                S = S + q[2]
    print(S if rev == 0 else S[::-1])
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

N = int(input())

explore = 1
for h in range(1,3500) :
    if not explore : break
    for n in range(1,3500) :
        if (4*h*n - N*n - N*h) == 0 :
            continue
        elif (N*h*n % (4*h*n - N*n - N*h) == 0) and (N*h*n//(4*h*n - N*n - N*h) > 0) :
            w = N*h*n//((4*h*n - N*n - N*h))
            ans = [h,n,w]
            explore = 0
            break

print(*ans)


### FIXED CODE ###

N = int(input())

explore = 1
for h in range(1,3500) :
    if not explore : break
    for n in range(1,3500) :
        if (4*h*n - N*n - N*h) == 0 :
            continue
        elif (N*h*n % (4*h*n - N*n - N*h) == 0) and (N*h*n//(4*h*n - N*n - N*h) > 0) :
            w = N*h*n//((4*h*n - N*n - N*h))
            ans = [h,n,w]
            explore = 0
            break

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

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

LRs = [list(map(int, input().split())) for i in range(m)]
LRs = [set(range(LRs[i][0], LRs[i][1] + 1)) for i in range(m)]

for i in range(m):
    if i == 0:
        union = LRs[i]
    else:
        union = union & LRs[i]

print(len(union))

### FIXED CODE ###

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

LRs = [list(map(int, input().split())) for i in range(m)]

under = 1
top = 10**6+10
for i in range(m):
    if LRs[i][0] > under:
        under = LRs[i][0]
    if LRs[i][1] < top:
        top = LRs[i][1]

if not top >= under:
    print(0)
else:

    print(top - under + 1)
### BUGGY CODE ###

def solve():
    n = int(input())

    # ord('B') == 66 (== 0 mod 3)
    # ord('R') == 82 (== 1 mod 3)
    # ord('G') == 71 (== 2 mod 3)
    s = [ord(c) % 3 for c in input()]

    accs = [[0] * (n + 1) for _ in range(3)]
    for i in range(3):
        for j in range(n):
            if i != s[j]:
                accs[i][j + 1] = accs[i][j]
            else:
                accs[i][j + 1] = accs[i][j] + 1

    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                continue
            residual = ({0, 1, 2} - {s[i], s[j]}).pop()
            ans += accs[residual][n] - accs[residual][j]
            if j + j - i + 1 <= n:
                ans -= accs[residual][j + j - i + 1] - accs[residual][j + j - i]
    return ans


print(solve())


### FIXED CODE ###

from itertools import accumulate
n = int(input())
s = input()

r_acc = [0] + list(accumulate([int(s[i] == 'R') for i in range(n)]))
g_acc = [0] + list(accumulate([int(s[i] == 'G') for i in range(n)]))
b_acc = [0] + list(accumulate([int(s[i] == 'B') for i in range(n)]))

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        si = s[i]
        sj = s[j]
        if si == sj:
            continue
        if (si == 'R' and sj == 'G') or (si == 'G' and sj == 'R'):
            ans += b_acc[n] - b_acc[j]
            if n >= j + j - i + 1:
                ans -= b_acc[j + j - i + 1] - b_acc[j + j - i]
        elif (si == 'R' and sj == 'B') or (si == 'B' and sj == 'R'):
            ans += g_acc[n] - g_acc[j]
            if n >= j + j - i + 1:
                ans -= g_acc[j + j - i + 1] - g_acc[j + j - i]
        else:
            ans += r_acc[n] - r_acc[j]
            if n >= j + j - i + 1:
                ans -= r_acc[j + j - i + 1] - r_acc[j + j - i]
print(ans)
### BUGGY CODE ###

(n, k) = [int(i) for i in input().split(" ")]
p = [int(i) for i in input().split(" ")]

maxNum = -1
maxIndex = [0, 0]
for i in range(n-k+1):
  s = 0
  for j in range(i, i+k, 1):
    s += p[j]
  if s > maxNum:
    maxNum = s
    maxIndex = [i, i+k]

dices = p[maxIndex[0]:maxIndex[1]]
exs = 0
for dice in dices:
  e = 0
  for i in range(1, dice+1):
    e += i 
  exs += e /dice
print(exs)

### FIXED CODE ###

(n, k) = [int(i) for i in input().split(" ")]
p = [int(i) for i in input().split(" ")]

s = 0
sums = [0]
for i in p:
  	s += i
  	sums.append(s)

maxNum = -1
maxIndex = [0, 0]
for i in range(len(sums)-k):
  if sums[i+k] - sums[i] > maxNum:
    maxNum = sums[i+k] - sums[i]
    maxIndex = [i, i+k-1]

dices = p[maxIndex[0]:maxIndex[1]+1]
e = 0
for dice in dices:
  e += sum(list(range(1, dice+1))) / dice
print(e)
### BUGGY CODE ###

import bisect


def memoize(f):
    cache = {}

    def func(x):
        if x not in cache:
            ret = cache[x] = f(x)
            return ret
        return cache[x]

    return func


@memoize
def get_bisect(y):
    return bisect.bisect(vy, (y, float('-inf')))


n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0

for x, y1, y2 in vx:
    it1, it2 = get_bisect(y1), get_bisect(y2 + 1)
    ans += sum(x1 <= x <= x2 for y, x1, x2 in vy[it1:it2])

print(ans)

### FIXED CODE ###

import bisect


class BIT:
    def __init__(self, n):
        self.tree = [0] * (n + 1)
        self.n = n

    def add(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & -i

    def _sum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def sum(self, l, h):
        return self._sum(h) - self._sum(l - 1)


n = int(input())
vx = []
xs = set()
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((y1, float('-inf'), x1))
        vx.append((y2, float('inf'), x1))
        xs.add(x1)
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vx.append((y1, x1, x2))
vx.sort()

bit = BIT(len(xs))
xs = [float('-inf')] + sorted(xs)
ix = {v: i for i, v in enumerate(xs)}
ans = 0

for y, j, x2 in vx:
    if j == float('-inf'):
        bit.add(ix[x2], 1)
    elif j == float('inf'):
        bit.add(ix[x2], -1)
    else:
        i1 = bisect.bisect_left(xs, j)
        i2 = bisect.bisect(xs, x2) - 1
        ans += bit.sum(i1, i2)

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

n = int(input())
l = list(map(int,input().split()))
l.sort()

m = len(l)
ans = 0
while m > 1:
    former = [0]*m
    for i in range(m):
        former[i] = l[i]
    l = []#初期化
    for i in range(1,m):
        num = former[0]
        l.append(num)
        if former[i]%num != 0:
            l.append(former[i]%num)
    l.sort()
    if l[0] == 1:
        ans = 1
        break
    m = len(l)
if ans == 1:
    print(ans)
else:
    print(l[0])

### FIXED CODE ###

import fractions
n = int(input())
l = list(map(int,input().split()))

gcd = l[0]
for i in range(1,n):
    gcd = fractions.gcd(l[i],gcd)
print(gcd)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
wa = []
while a != []:
    t = a[0]
    if len(a) == 1:
        wa.append(t)
    elif a[0] != a[1]:
        wa.append(t)
    han = int(max(a)/t)+2
    bai = [i*t for i in range(1, han)]
    a = [i for i in a if i not in bai]
    

print(len(wa))

### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n=int(input())
    A=list(map(int, input().split()))
    counts=[0]*(10**6+5)
    for AA in A:
        counts[AA]+=1
    ans=0
    for i in range(1,10**6+5):
        if counts[i]>0:
            for j in range(i+i,10**6+5,i):
                counts[j]=-1
        if counts[i]==1:
            ans+=1
    print(ans)
        

        
    


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

n = int(input())

s_input_list = []

for i in range(n):
    tmp = input()
    s_input_list.append(tmp)

s_sorted_list = []
for s in s_input_list:
    tmp = list(s)
    tmp.sort()
    s_sorted_list.append(tmp)

#print(s_sorted_list)

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if(s_sorted_list[i] == s_sorted_list[j]):
            ans = ans +1
print(ans)

### FIXED CODE ###

n = int(input())
from collections import defaultdict


s_input_list = []

for i in range(n):
    tmp = input()
    s_input_list.append(tmp)


d = defaultdict(list)

s_sorted_list = []
for s in s_input_list:
    tmp = list(s)
    tmp.sort()
    
    s_sorted_list.append("".join(tmp))

#print(s_sorted_list)

ans = 0
for i in range(n):
    d[s_sorted_list[i]].append(i)

for key,value in d.items():
    v = len(value)
    ans = ans + int(v*(v-1)/2)

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

N,A,B,K = map(int,input().split())
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
#fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

P = 500
pascal = [None] * (P+1)
pascal[0] = [1,0]
for n in range(1,P+1):
    pascal[n] = [1]
    for r in range(1,n+1):
        pascal[n].append(pascal[n-1][r-1] + pascal[n-1][r])
    pascal[n].append(0)

def ncr(n,r):
    if n <= P:
        return pascal[n][r]
    else:
        return mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)


### FIXED CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)