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

N = int(input())
S= input()
count = 0
R,G,B = [],[],[]
for i in S:
    if i == 'R':
        R.append(count)
    elif i == 'G':
        G.append(count)
    else:
        B.append(count)
    count += 1
sub = 0
for r in R:
    for g in G:
        for b in B:
            if b==2*r-g or b==2*g-r or b==(r+g)/2:
                sub +=1
ans = len(R)*len(G)*len(B) -sub
print(ans)
       

### FIXED CODE ###

N = int(input())
S= input()
sub = 0
R,G,B = [],[],[]
r = S.count('R')
g = S.count('G')
b = S.count('B') 
for i in range(N):
    for j in range(i+1,N):
        if 2*j-i > N-1:
            break
        if S[i] != S[j] and S[2*j-i] != S[i] and S[2*j-i] != S[j]:
            sub += 1
ans = r*g*b -sub
print(ans)
### BUGGY CODE ###

import math
A, B, N = map(int,input().split())
x = [i for i in range(1,N+1)]
res = [math.floor(A*x[i]/B) - (A*math.floor(x[i]/B)) for i in range(N)]
print(max(res))

### FIXED CODE ###

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

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

def main():
    N,M=map(int,input().split())
    A = list(map(int, input().split()))
    A.sort()
    while M>0:
        a = A.pop()
        a //= 2
        M -= 1
        bisect.insort(A, a)
    print(sum(A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
import heapq

def main():
    _,M=map(int,input().split())
    A = []
    for a in list(map(int, input().split())):
        heapq.heappush(A, -a)
    while M>0:
        a = -heapq.heappop(A)
        a //= 2
        M -= 1
        heapq.heappush(A, -a)
    print(-sum(A))

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

import numpy as np
n = int(input())
l = np.array(list(map(int, input().split())))
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[k] >= l[j] + l[i]:
                break
            if l[j] < l[k] + l[i] and l[i] < l[k] + l[j]:
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
    k = i+1
    for j in range(i+1, n):
        while k < n and l[k] < l[i] + l[j]:
            k += 1
            ans += k - (j+1)
print(ans)
### BUGGY CODE ###

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

ls = [-1,-1,N,N]
ans = 0
for i in range(N,0,-1):
    x = P.index(i)
    ind = bisect.bisect(ls,x)
    bisect.insort(ls,x)
    L2 = ls[ind-2]
    L1 = ls[ind-1]
    R1 = ls[ind+1]
    R2 = ls[ind+2]
    L = (L1-L2)*(R1-x)
    R = (R2-R1)*(x-L1)
    ans += i * (L+R)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
P = list(map(int,input().split()))

'''
import random
N = 100000
P = list(range(1,N+1))
#random.shuffle(P)
'''

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i = i//2
            j = j//2
        return s

P2 = [[[p,i],[0,0]] for i,p in enumerate(P)]

max2 = lambda x,y : sorted(x+y,reverse=True)[:2]

seg = SegmentTree(P2,max2,[[0,0],[0,0]])

cand = [[0,N]]

ans = 0
visited = set([])
while cand:
    #print(cand)
    temp = []
    for l,r in cand:
        if r-l < 2:
            continue
        if (l,r) in visited:
            continue
        visited.add((l,r))
        (m1,i1), (m2,i2) = seg.get(l,r)
        #print(P[l:r],m1,m2)
        i1,i2 = (i1,i2) if i1 < i2 else (i2,i1)
        ans += m2 * (i1-l+1) * (r-i2)
        temp.append([l,i2])
        temp.append([i1+1,r])
    cand = temp

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

S = input()
N = len(S)
for _ in range(N):
    S = S.replace('01','').replace('10','')
    if S.count('01') == 0 and S.count('10') == 0:
        break
print(N - len(S))

### FIXED CODE ###

S = input()
r = S.count('0')
b = S.count('1')
print(min(r,b)*2)
### BUGGY CODE ###

n, k = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]

min_area = 10**100
for a in lst:
    for b in lst:
        for c in lst:
            for d in lst:
                count = 0
                for e in lst:
                    if a[0] <= e[0] <= b[0] or a[0] >= e[0] >= b[0]:
                        if c[1] <= e[1] <= d[1] or c[1] >= e[1] >= d[1]:
                            count += 1
                if count >= k:
                    area = abs(a[0] - b[0]) * abs(c[1] - d[1])
                    if area < min_area:
                        min_area = area
print(min_area)

### FIXED CODE ###

n, k = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]

answer = 10**100
sortx = sorted(lst, key = lambda x: x[0])
for a, pt1 in enumerate(sortx[:n-k+1]):
    for b, pt2 in enumerate(sortx[a+k-1:]):
        #print(a,b)
        sorty = sorted(sortx[a:a+k+b], key = lambda x: x[1])
        sorty_len = len(sorty)
        for c, pt3 in enumerate(sorty[:sorty_len-k+1]):
            #print(len(sorty), c, k)
            pt4 = sorty[c+k-1]
            #print(pt1, pt2, pt3, pt4)
            if pt3[1] <= pt1[1] and pt3[1] <= pt2[1] and pt4[1] >= pt1[1] and pt4[1] >= pt2[1]:
                answer = min(answer, (pt2[0] - pt1[0]) * (pt4[1] - pt3[1]))
print(answer)
### BUGGY CODE ###

N=int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 4*h*n-N*n-h*N==0:
            continue
        w=(N*h*n)/(4*h*n-N*n-h*N)
        if w==int(w) and w>=1:
            print(h,n,int(w))
            exit()


### FIXED CODE ###

N=int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 4*h*n-N*n-h*N==0:
            continue
        w=(N*h*n)/(4*h*n-N*n-h*N)
        if w==int(w) and w>=1:
            print(h,n,int(w))
            exit()
### BUGGY CODE ###

N,K = map(int,input().split())
XY = list(list(map(int,input().split()))for i in range(N))

ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
XY = []

for i in range(N):
    x,y = map(int,input().split())
    XY.append((x,y))


ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
l = []
wa = 0
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    wa += a
    l.append([a,b,c])
dp = [[wa + 1 for i in range(2**n)] for i in range(m+1)]
bit = 2**n
#print(l)
for i in range(1,m+1):
    a,b,c = l[i-1]
    bitc = 0
    for x in c:
        bitc += 2**(x-1)
    for j in range(bit):
        j2 = j
        mod = 1
        for k in range(n):
            if (j >> k) & 1:
                continue
            else:
                if (bitc >> k) & 1:
                    j2 += 2**k
        #print(i,j,j2)
        if j == 0:
            dp[i][j2] = min([dp[i-1][j2],a,dp[i][j2]])
        else:
            dp[i][j2] = min([dp[i-1][j]+a,dp[i-1][j2],dp[i][j2]])
        if j2 != j:
            dp[i][j] = dp[i-1][j]
ans = dp[m][bit-1]
#print(dp)
if ans <= wa:
    print(dp[m][bit-1])
else:
    print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
l = []
wa = 0
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    wa += a
    l.append([a,b,c])
dp = [[wa + 1 for i in range(2**n)] for i in range(m+1)]
bit = 2**n
#print(l)
for i in range(1,m+1):
    a,b,c = l[i-1]
    bitc = 0
    for x in c:
        bitc += 2**(x-1)
    for j in range(bit):
        j2 = j
        mod = 1
        for k in range(n):
            if (j >> k) & 1:
                continue
            else:
                if (bitc >> k) & 1:
                    j2 += 2**k
        #print(i,j,j2)
        if j == 0:
            dp[i][j2] = min([dp[i-1][j2],a,dp[i][j2]])
        else:
            dp[i][j2] = min([dp[i-1][j]+a,dp[i-1][j2],dp[i][j2]])
        if j2 != j:
            dp[i][j] = dp[i-1][j]
ans = dp[m][bit-1]
#print(dp)
if ans <= wa:
    print(dp[m][bit-1])
else:
    print(-1)
### BUGGY CODE ###

import math
X = int(input())

for a in range(1, 5000):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1, 5000):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)

        if an == X:
            print(a, b)
            exit()


### FIXED CODE ###

import math
X = int(input())

for a in range(1, 1500):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1500, 1500):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)
        if an < 0:
            break

        if an == X:
            print(a, b)
            exit()
### BUGGY CODE ###

import sys
import bisect
sys.setrecursionlimit(10 ** 7)

# Xor
# ビット毎に独立
# k-bit目を二分探索


N = int(input())

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

ans = 0
for i in range(29):
    NA = [a % 2 ** (i + 1) for a in A]
    NB = [b % 2 ** (i + 1) for b in B]
    NB.sort()

    T = 2 ** i
    cnt = 0
    for a in NA:
        # [T-a,2T-a)
        ta1 = T - a
        ta2 = T * 2 - a
        i1 = bisect.bisect_left(NB, ta1)
        i2 = bisect.bisect_left(NB, ta2) - 1
        cnt += i2 - i1

        # [3T-a,4T-a)
        ta3 = T * 3 - a
        ta4 = T * 4 - a
        i3 = bisect.bisect_left(NB, ta3)
        i4 = bisect.bisect_left(NB, ta4) - 1
        cnt += i4 - i3

    if cnt % 2 == 1:
        ans += 2 ** i

print(ans)


### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

# Xor
# ビット毎に独立
# k-bit目を二分探索


N = int(input())

A = np.array(input().split(), dtype=np.int64)
B = np.array(input().split(), dtype=np.int64)


mask = 1

ans = 0
for i in range(29):
    NA = A & mask
    NB = B & mask
    NA.sort()
    NB.sort()

    T = 2 ** i
    x1, x2, x3 = [np.searchsorted(NB, t - NA).sum() for t in [T, 2 * T, 3 * T]]
    zero_cnt = x1 + (x3 - x2)
    if (N*N - zero_cnt) % 2 == 1:
        ans += 2 ** i

    mask = mask * 2 + 1

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

S = input()
Q = (int)(input())

for i in range(Q):
    query = (input())
    if query=="1":
        S=S[::-1]
    else:
        query = query.split(" ")
        if query[1] == "1":
            S = query[2]+S
        else:
            S = S+query[2]

print(S)

### FIXED CODE ###

S = input()
Q = (int)(input())

mae = ""
usiro =""

r_num=0

for i in range(Q):
    query = (input())
    if query=="1":
        #kari = mae
        #mae=usiro[::-1]
        #usiro=kari[::-1]
        r_num+=1
    else:
        query = query.split(" ")
        if query[1] == "1":
            if r_num%2==0:
                mae = query[2]+mae
            else:
                usiro += query[2]
        else:
            if r_num %2 ==0:
                usiro += query[2]
            else:
                mae = query[2]+mae
if r_num%2 == 1:
    print(usiro[::-1]+S[::-1]+mae[::-1])
else:
    print(mae+S+usiro)
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    for ii in range(i + 1, N):
        for iii in range(ii + 1, N):
            if L[i] + L[ii] > L[iii] and \
                L[i] + L[iii] > L[ii] and \
                L[ii] + L[iii] > L[i]:
                ans += 1

print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0

for i in range(N - 2):
    a = L[i]
    for ii in range(i + 1, N - 1):
        b = L[ii]
        iii = bisect.bisect_left(L, a + b)
        ans += iii - ii - 1
            
print(ans)
### BUGGY CODE ###

A,B,N=map(int, input().split())
ans=[]
for i in range(1,N+1):
    ans.append(int(A*i/B)-A*int(i/B))
print(max(ans))

### FIXED CODE ###

A,B,N=map(int, input().split())
if N>=B-1:
    print(int(A*(B-1)/B)-A*int((B-1)/B))
else:
    print(int(A*N/B)-A*int(N/B))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
f.sort()
a.sort()
a.reverse()
l=0
r=10**12+1
import math
while r-l>1:
	mid=(l+r)/2
	cnt=0
	for i in range(n):
		if a[i]*f[i]>mid:
			cnt+=a[i]-mid//f[i]
	if cnt<=k:
		r=mid
	else:
		l=mid
print(int(r))



### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
f.sort()
a.sort()
a.reverse()
l=0
r=10**12+1
import math
while r-l>1:
	mid=(l+r)/2
	cnt=0
	for i in range(n):
		if a[i]*f[i]>mid:
			cnt+=a[i]-mid//f[i]
	if cnt<=k:
		r=mid
	else:
		l=mid
print(int(r))
### BUGGY CODE ###

def retrun_index(c_lis):
    return [i for i, x in enumerate(c_lis) if x==1]

n, m = map(int, input().split())
lis = [1, 1] + [0]*(n-1)
c = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a][b] = 1
    c[b][a] = 1
ind = retrun_index(c[1])
for i in ind:
    lis[i] = 1
i = 0
while True:
    if i>=len(ind):
        break
    t = ind[i]
    te = retrun_index(c[t])
    for j in te:
        if lis[j] == 0:
            lis[j] = t
            ind.append(j)
    i += 1

    
if lis.count(0) > 0:
    print("No")
else:
    print("Yes")
    for i in lis[2:]:
        print(i)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
lis = [0]*(n+1)
c = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        lis[i] = now
        que.append(i)
if 0 in lis[2:]:
    print("No")
else:
    print("Yes")
    for i in lis[2:]:
        print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit(cache=True)
def solve(N, costX, costY):
    ans = [INF] * (N + 1)

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = np.minimum(cx, cy).sum()
        ans[M] = min(ans[M], cost)

    return ans

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=False)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = solve(N, costX, costY)
    print(*ans, sep='\n')

sol()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

from functools import reduce

def factorization(n):
    '''
    素因数分解の結果を返す
    例： n = 100 の時、[2, 2, 5, 5] 
    '''
    arr = []
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                arr.append(i)
                tmp //= i
    if tmp != 1:
        arr.append(tmp)
    if arr == []:
        arr.append(n)
    return arr


def combination(l):
    res = []
    for i in range(1, 2**len(l)):
        tmp = []
        for j in range(len(l)):
            if (i >> j) &1 == 1:
                tmp.append(l[j])
        res.append(tmp)
    return res


def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


def solve():
    N = int(input())
    F = factorization(N)
    ans = N - 1
    for c in get_unique_list(combination(F)):
        t = reduce(lambda x, y: x * y, c)
        ans = min(ans, N // t - 1 + t - 1)
    print(ans)

if __name__ == "__main__":
    solve()


### FIXED CODE ###

def make_divisors(n):
    '''
    nの約数の配列を返す
    '''
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def solve():
    N = int(input())
    D = make_divisors(N)
    ans = N - 1
    for d in D:
        ans = min(ans, N // d - 1 + d - 1)
    print(ans)

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[None]*(w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
for i in range(1, n+1):
    wi, vi = wv[i-1]
    for j in range(w+1):
        if j < wi:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)
print(dp[-1][-1])

### FIXED CODE ###

def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

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

def gcd(a,b):
    g=1
    while b!=0:
        g=a%b
        a=b
        b=g
    return a
    
def gcd_list(numbers):
    # print(numbers)
    g=numbers[0]
    for i in range(n-1):
        g=gcd(g,numbers[i])
    return g

n=int(input())
a=list(map(int,input().split()))
gcd_without_i=[gcd_list(a[:i]+a[i+1:]) for i in range(n)]
# print(gcd_without_i)
print(max(gcd_without_i))


### FIXED CODE ###

def gcd(a,b):
    if a*b<0:
        return -a*b
    while b!=0:
        tmp=a%b
        a=b
        b=tmp
    return a

# def gcd_list(numbers):
#     # print(numbers)
#     g=numbers[0]
#     for i in range(n-1):
#         g=gcd(g,numbers[i])
#     return g
#
# n=int(input())
# a=list(map(int,input().split()))
# gcd_without_i=[gcd_list(a[:i]+a[i+1:]) for i in range(n)]
# # print(gcd_without_i)
# print(max(gcd_without_i))

n=int(input())
a=list(map(int,input().split()))
# gcd_lhs[i]=gcd(a[0],...,a[i-1])
gcd_lhs=[-1 for _ in range(n)]
# gcd_rhs[i]=gcd(a[i+1],...,a[n-1])
gcd_rhs=[-1 for _ in range(n)]
gcd_lhs[1]=a[0]
gcd_rhs[n-2]=a[n-1]
for i in range(1,n):
    gcd_lhs[i]=gcd(gcd_lhs[i-1],a[i-1])
    gcd_rhs[n-1-i]=gcd(gcd_rhs[n-i],a[n-i])

gcd_without_i=[gcd(gcd_lhs[i],gcd_rhs[i]) for i in range(n)]
print(max(gcd_without_i))
### BUGGY CODE ###

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

N = 998244353

def fac(n,r,N):
    ans=1
    for i in range(r):
        ans=ans*(n-i)%N
    return ans

def combi(n,r,N):
    r= min(r, n-r)
    ans = fac(n,r,N)*pow(fac(r,r,N),N-2,N)%N
    return ans

ans=0
if k<n//2:
    for i in range(k+1):
        ans+=m*combi(n-1,i,N)*pow(m-1,n-1-i,N)%N
        ans%=N
    print(ans)
else:
    for i in range(k+1,n):
        ans+=m*combi(n-1,i,N)*pow(m-1,n-1-i,N)%N
        ans%=N
    ans = pow(m,n,N)-ans
    if ans < 0:
        ans +=N
    print(ans)


### FIXED CODE ###

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

N = 998244353

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % N)
    inverse.append(pow(factorial[-1], N - 2, N))

def combi(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % N

ans=0
if k<n//2:
    for i in range(k+1):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    print(ans)
else:
    for i in range(k+1,n):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    ans = pow(m,n,N)-ans
    if ans < 0:
        ans +=N
    print(ans)
### BUGGY CODE ###

S=input()
MOD=10**9+7
dp=[0]*13
dp[0]=1
for s in S:
    p=[x for x in dp]
    dp=[0]*13
    if s=="?":
        a=range(10)
    else:
        a=[int(s)]
    for i in range(13):
        for x in a:
            dp[(10*i+x)%13]+=p[i]
    dp=[x%MOD for x in dp]
print(dp[5])

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[0]*13
dp[0]=1
for s in S:
    p=[x for x in dp]
    dp=[0]*13
    if s=="?":
        a=range(10)
    else:
        a=[int(s)]
    for i in range(13):
        for x in a:
            dp[(10*i+x)%13]+=p[i]
    dp=[x%MOD for x in dp]
print(dp[5])
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

num = int(input())
a = list(map(int, input().split()))
b = 0
for i in a:
  for f in make_divisors(i):
    if f in a:
      if f == i and a.count(f) > 1:
        b += 1
        break
      elif f != i:
        b += 1
        break
print(num - b)     

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * a[-1]
c = Counter(a)
for i in a:
    for j in range(i, a[-1]+1, i):
        dp[j-1] += 1
ans = 0
for i in a:
    if dp[i-1] == 1 and c[i]:
        ans += 1
print(ans)