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

n = int(input())
L = list(map(int, input().split()))
x = [0] * 1010
for l in L:
  x[l] += 1

ans = 0;
for a in range(1, 1001):
  for b in range(a, 1001):
    for c in range(b, 1001):
      if c >= a + b:
        break
      if a == b == c:
        ans += x[a] * (x[b]-1) * (x[c]-2) // 6
      elif a == b:
        ans += x[a] * (x[b]-1) // 2
      elif b == c:
        ans += x[a] * x[b] * (x[c]-1) // 2
      else:
        ans += x[a] * x[b] * x[c]

print(ans)

### FIXED CODE ###

n = int(input())
L = list(map(int, input().split()))
x = [0] * 1010
for l in L:
  x[l] += 1

ans = 0;
for a in range(1, 1001):
  if x[a] == 0:
    continue
  for b in range(a, 1001):
    if x[b] == 0:
      continue
    for c in range(b, 1001):
      if x[c] == 0:
        continue
      if c >= a + b:
        break
      if a == b == c:
        ans += x[a] * (x[b]-1) * (x[c]-2) // 6
      elif a == b:
        ans += x[a] * (x[b]-1) * x[c] // 2
      elif b == c:
        ans += x[a] * x[b] * (x[c]-1) // 2
      else:
        ans += x[a] * x[b] * x[c]

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

N = int(input())
X = int(input(), 2)

def popcount(n):
    return bin(n).count('1')
memo = {1:1}
def f_count(n):
    co_n = n
    ans = 0
    while n != 0:
        if n in memo:
            ans += memo[n]
            memo[co_n] = ans
            return ans
        n %= popcount(n)
        ans += 1
    memo[co_n] = ans
    return ans

for i in range(N):
    x = X
    if X >> (N-1 -i) & 1:
        x -= 2**(N-1 -i)
    else:
        x += 2**(N-1 -i)
    print(f_count(x))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)
### BUGGY CODE ###

N = int(input())

H = list(map(int,input().split()))

cnt = 0
t = 0

for l in range(N):
  r = l + 1
  while r < N and H[r-1] >= H[r]:
    cnt += 1
    r += 1
  t = max(t,cnt)
  cnt = 0

print(t)

### FIXED CODE ###

N = int(input())

H = list(map(int,input().split()))

H = H[::-1]

l = 0
cnt = 0
t = 0

while l < N - 1:
  if H[l] <= H[l+1]:
    cnt += 1
  else:
    t = max(t,cnt)
    cnt = 0
  l += 1

print(max(t,cnt))
### BUGGY CODE ###

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

ans = 0
s = [(K, V[:], [], False)]
while s:
    cnt, v, bag, flag = s.pop()
    ans = max(ans, sum(bag))
    if cnt > 0 and v and not flag:
        s.append((cnt-1, v[1:], bag + [v[0]], False))
        s.append((cnt-1, v[:-1], bag + [v[-1]], False))
    if cnt > 0 and bag:
        bag.sort()
        s.append((cnt-1, [bag[0]] + v, bag[1:], True))
        s.append((cnt-1, v + [bag[0]], bag[1:], True))

print(ans)


### FIXED CODE ###

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

ans = 0
for l in range(K+1):
    for r in range(K-l+1):
        if l + r < N:
            bag = V[:l] + V[N-r:] + [0]
            rest_ope = K-l-r
        else:
            bag = V[:]
            rest_ope = K - N
        for _ in range(rest_ope):
            min_bag = min(bag)
            if min_bag < 0 and rest_ope > 0:
                bag.remove(min_bag)
                rest_ope -= 1
        else:
            ans = max(ans, sum(bag))

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

from collections import Counter


def inpl():
    return list(map(int, input().split()))


N, A = inpl()
X = inpl()
cX = Counter(X)

dp = [[[0 for _ in range(N * max(X) + 1)] for j in range(i + 1)]
      for i in range(N + 1)]

dp[0][0][0] = 1
for i in range(1, N + 1):
    x = X[i - 1]
    for j in range(i + 1):
        for k in range(N * max(X) + 1):
            # print(i, j, k)
            if j == i and k - x < 0:
                dp[i][j][k] = 0
            elif j == i and k - x >= 0:
                dp[i][j][k] = dp[i - 1][j - 1][k - x]
            elif k - x < 0 or j == 0:
                dp[i][j][k] = dp[i - 1][j][k]
            else:
                dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x]

ans = 0
for j in range(1, N + 1):
    if j * A > N * max(X):
        continue
    ans += dp[N][j][j * A]
print(ans)


### FIXED CODE ###

def inpl():
    return list(map(int, input().split()))


N, A = inpl()
X = inpl()
maxX = max(X)

dp = [[[0 for _ in range(N * maxX + 1)] for j in range(i + 1)]
      for i in range(51)]

dp[0][0][0] = 1
for i in range(N):
    x = X[i - 1]
    for j in range(i + 1):
        for k in range(N * maxX + 1):
            # print(i, j, k)
            if dp[i][j][k] == 0:
                continue
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x] += dp[i][j][k]

ans = 0
for j in range(1, N + 1):
    if j * A > N * maxX:
        continue
    ans += dp[N][j][j * A]
print(ans)
### BUGGY CODE ###

n = int(input())
c = input()
l = list(c)
ans = 0
a = 0
b = n
while c.count("WR") > 0 :
   for i in range(a,b) :
       if l[i] == "W" :
           l[i] = "R"
           a = i
           break
   for j in reversed(range(a,b)) :
       if l[j] == "R" :
           l[j] = "W"
           b = j
           break
   c = ''.join(l)
   ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
c = list(input())
w = 0
r = c.count("R")
ans = r
for i in range(n) :
    if c[i] == "W" :
        w += 1
    else :
        r -= 1
    if ans > max(w,r) :
        ans = max(w,r)

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

S = input().rstrip()
Q = int(input().rstrip())
reversed = False
for _ in range(Q):
    l = input().rstrip()
    if l.startswith('1'):
        reversed = False if reversed else True
    else:
        _, F, C = l.split()
        if F == '1':
            if reversed:
                S = S + C
            else:
                S = C + S
        else:
            if reversed:
                S = C + S
            else:
                S = S + C
if reversed:
    ret = S[::-1]
else:
    ret = S
print(ret)


### FIXED CODE ###

S = input().rstrip()
Q = int(input().rstrip())
reversed = False
from collections import deque
q = deque()
q.extend(list(S))
for _ in range(Q):
    l = input().rstrip()
    if l.startswith('1'):
        reversed = False if reversed else True
    else:
        _, F, C = l.split()
        if F == '1':
            if reversed:
                q.append(C)
            else:
                q.appendleft(C)
        elif F == '2':
            if reversed:
                q.appendleft(C)
            else:
                q.append(C)
ret = ''.join(list(q)[::-1]) if reversed else ''.join(list(q))
print(ret)
### BUGGY CODE ###

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

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

ans = 0
all = {'R', 'G', 'B'}
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)


### 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 ###

data = {}
N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())

for a in A:
    data[a] = data.get(a, 0) + 1

for _ in range(Q):
    b, c = map(int, input().split())
    if data.get(b):
        data[c] = data.get(c, 0) + data.pop(b)
    print(sum([k * v for k, v in data.items()]))

### FIXED CODE ###

data = {}
total = 0
N = int(input())

for a in input().split():
    a = int(a)
    data[a] = data.get(a, 0) + 1
    total += a

Q = int(input())

for _ in range(Q):
    b, c = map(int, input().split())
    diff = c - b
    count = data.get(b)
    if count:
        data[c] = data.get(c, 0) + data.pop(b)
        total += diff * count
    print(total)
### BUGGY CODE ###

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

cnt=0
s=0
for i in range(n-k+1):
    tmp=p[i:i+k]
    if s < sum(tmp):
        cnt = i
        s = sum(tmp)

ans=0
for i in range(cnt, cnt+k):
    tmp=0
    ans += (1+p[i])*p[i]/2/p[i]

print(ans)

### FIXED CODE ###

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

ex = []
for i in range(n):
    ex += [(1+p[i])]

s = sum(ex[0:k])
t = s
for i in range(n-k):
    s = s-ex[i]+ex[i+k]
    t = max(t, s)

print(t/2)
### BUGGY CODE ###

#ABC072-C
import collections
import itertools

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

cnt = 0

for i in range(len(a)):
    tmp = a.count(a[i]-1) + a.count(a[i]) + a.count(a[i]+1)
    if tmp > cnt:
        cnt = tmp
        
print(cnt)


### FIXED CODE ###

#ABC072-C
n = int(input())
a = list(map(int,input().split()))
 
cnt = [0] * 100002


for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i+2] += 1
    
    

    
        
print(max(cnt))
### BUGGY CODE ###

X = int(input())
def modpow(a, n, mod):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % mod
        a *= a
        a = a % mod
    return ret
i = 0
L = list()
while True:
    num = modpow(i,5,X)
    if num in L:
        j = L.index(num)
        ret = '{} {}'.format(i,j)
        print(ret)
        break
    else:
        L.append(num)

### FIXED CODE ###

X = int(input())
L = list()
i = 0
while True:
    if i ** 5 > 10 ** 11:
        break
    L.append(i ** 5)
    i += 1
flag = False
ret = ''
for i in range(len(L)):
    if flag:
        break
    for j in range(i+1, len(L)):
        if L[j] - L[i] == X :
            ret ='{} {}'.format(j,i)
            flag = True
            break
        if L[j] + L[i] == X :
            ret ='{} {}'.format(j,-i)
            flag = True
            break
print(ret)
### BUGGY CODE ###

n = int(input())
aList = list(map(int, input().split()))
col = aList[:n-1]
row = aList[1:]
ansSum = 0
for i in range(n-1):
    for j in range(i,n-1):
        ansSum += col[i]*row[j]
print(ansSum % (7+10**9))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
array_sum_square = sum(A)**2
individual_square_sum = 0
for i in range(0, n, 1):
    individual_square_sum += A[i]**2
print((array_sum_square - individual_square_sum) // 2 % (7 + 10 ** 9))
### BUGGY CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

ans = []
for i in range(N):
    flg = 0
    for j in range(len(ans)):
        if S[i] == ans[j]:
            flg = 1
            break
    if flg == 0:
        ans.append(S[i])

print(len(ans))

### FIXED CODE ###

N = int(input())

ans = set()

for i in range(N):
    S = input()
    if S in ans:
        continue
    else:
        ans.add(S)

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

n,m = map(int,input().split())
A = [int(input()) for _ in range(m)]
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])


### FIXED CODE ###

n,m = map(int,input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])
### BUGGY CODE ###

N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

stack=[]
INF=10**5*3
seen=[[INF for i in range(3)] for j in range(N)]
stack.append([S,0,1])
ans=INF
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      if ans>turn:
        ans=turn
      continue
    step=0
    turn+=1
  if seen[v][step]<=turn:
    continue
  seen[v][step]=turn
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  if ans==INF:
    print(-1)
  else:
    print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

from collections import deque
stack=deque()
seen=[[False for i in range(3)] for j in range(N)]
stack.append([S,0,1])
while stack:
  node=stack.popleft()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      print(turn)
      break
    step=0
    turn+=1
  if seen[v][step]:
    continue
  seen[v][step]=True
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
ab_lst = [list(map(int, input().split())) for _ in range(n-1)]
px_lst = [list(map(int, input().split())) for _ in range(q)]

res = [0] * (n+1)
neighbor = [[] for _ in range(n+1)]
for edge in ab_lst:
    neighbor[edge[0]].append(edge[1])

root_value = [0] * (n+1)
for px in px_lst:
    root_value[px[0]] += px[1]
    
def dfs(root, value):
    res[root] += value
    if neighbor[root] != []:
        for i in neighbor[root]:
            dfs(i, value + root_value[i])

dfs(1, root_value[1])
            
for i in res[1:]:
    print(i, end=" ")

### FIXED CODE ###

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

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

root_value = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    root_value[p] += x

res = [0] * (n+1)
queue = [(1, root_value[1])]
while len(queue) > 0:
    pair = queue.pop()
    res[pair[0]] += pair[1]
    if neighbor[pair[0]] != []:
        for i in neighbor[pair[0]]:
            queue.append((i, pair[1] + root_value[i]))
    
for i in res[1:]:
    print(i, end=" ")
### BUGGY CODE ###


# ===== Main ==== #
def main():
    # =Input Space = #
    listA=[]
    while True:
        try:
            listA.append(list(map(int,input().split())))
        except:
            break;
    N = listA[0][0]
    A = listA[1]
    B = listA[2]

    if sum(A) < sum(B):
        print(-1)
        return 0
    C = []
    for i in range(len(A)):
        num = A[i] - B[i]
        C.append(num)
    D = C.copy()

    while True:
        if len([i for i in C if i < 0]) == 0:
            break
        max_ = max(C)
        max_index = C.index(max_)
        count = -1
        for i in C:
            count += 1
            if i < 0:
                if max_ <= abs(i):
                    C[count] += max_
                    max_ = 0
                    break
                else:
                    C[count] = 0
                    max_ -= abs(i)
        C[max_index] = max_

    count = 0
    for i in range(len(C)):
        if D[i] != C[i]:
            count += 1
    print(count)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    if sum(A) < sum(B):
        return -1

    C = [a-b for a,b in zip(A,B)]
    plus = [x for x in C if x > 0]
    minus = [x for x in C if x < 0]
    change = sum(minus)
    count = 0
    if change == 0:
        return 0

    for i in sorted(plus,reverse=True):
        if change >= 0:
            break
        change += i
        count += 1
    return count + len(minus)

print(solve())
### BUGGY CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
    left = v if v < 100001 else 100001
    right = left + ans + 1 if left + ans + 1 < 100001 else 100001
    for i in range(left, right)[::-1]:
        if bag[i-v] + w < min(bag[i],W+1):
            bag[i] = bag[i-v] + w
            if i > ans:
                ans = i
print(ans)


### FIXED CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

s = input()
l = len(s)
count = [0] * 2019
res = 0
count[res] = 1
for i in range(1, l+1):
    res += int(s[-i]) * 10 ** (i-1)
    res %= 2019
    count[res] += 1
print(int(sum([m*(m-1)/2 for m in count])))

### FIXED CODE ###

s = input()
s = s[::-1]
l = len(s)
count = [0] * 2019
res = 0
count[res] = 1
d = 1
for i in s:
    res += int(i) * d
    res %= 2019
    count[res] += 1
    d *= 10
    d %= 2019
print(int(sum([m*(m-1)/2 for m in count])))
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

if A == [3, 14, 159, 2, 6, 53] and B == [58, 9, 79, 323, 84, 6] and C == [2643, 383, 2, 79, 50, 288]:
  print(87)
  exit()

count = 0

A = sorted(A)
C = sorted(C)

for i in range(N):
  a = bisect_left(A, B[i])
  c = bisect_left(C, B[i])
  bis_a = len(A[:a])
  bis_c = len(C[c:])
  count += (bis_a*bis_c)

print(count)

### FIXED CODE ###

from bisect import *
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

count = 0

for i in range(N):
  a = bisect_left(A, B[i])
  c = bisect(C, B[i])
  c = N - c
  count += (a*c)

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

import numpy as np
import math
x = int(input())
ys = []
i = 1
while i**2 < x:
    if x%i == 0:
        ys.append(i)
        ys.append(x//i)
    i += 1
if i**2 == x:
    ys.append(i)

f = False

for j in ys:
    for i in range(10**100):
        if i**5-(i-j)**5 == x:
            print(i,i-j)
            break
        elif i**5-(i-j)**5 > x and i-j > 0:
            break
    if f:
        break

### FIXED CODE ###

import numpy as np
import math
x = int(input())
ys = []
i = 1
while i**2 < x:
    if x%i == 0:
        ys.append(i)
        ys.append(x//i)
    i += 1
if i**2 == x:
    ys.append(i)

f = False

for j in ys:
    for i in range(10**3):
        if i**5-(i-j)**5 == x:
            print(i,i-j)
            break
        elif i**5-(i-j)**5 > x and i-j > 0:
            break
    if f:
        break
### BUGGY CODE ###

A,B=map(int,input().split())
lst=set()
i=2
while i<=A and i<=B:
    #print(i,A,B,lst)
    if A%i==0 and B%i==0:
        flag=1
        for l in lst:
            if i%l==0:
                flag=0
                break
        A=A//i
        B=B//i
        if flag:
            lst.add(i)
    i+=1


lst.add(1)
#print(lst)
print(len(lst))


### FIXED CODE ###

A,B=map(int,input().split())
lst=set()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)
### BUGGY CODE ###

n = 50001
is_prime = [True for i in range(n)]
is_prime[0] = is_prime[1] = False
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = False
        j += i
    i += 1

cnt_pair = [0 for i in range(n)]
for i in range(3, n//2, 2):
    if is_prime[i]:
        for j in range(i, n - i, 2):
           if is_prime[j]:
               cnt_pair[i + j] += 1

while True:
    n = int(input())
    if n == 0:
        break
    print(cnt_pair[n])



### FIXED CODE ###

n = 50001
is_prime = [i for i in range(n)]
is_prime[0] = is_prime[1] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = 0
        j += i
    i += 1

prime_set  = set(is_prime)
prime_set.remove(0)
prime_list = sorted(list(prime_set))

while True:
    cnt = 0
    n = int(input())
    if n == 0:
        break
    for i in prime_list:
        if i > n//2:
            break
        if n - i in prime_set:
            cnt += 1
    print(cnt)
### BUGGY CODE ###

L,R = map(int,input().split())
ans = []
if R-L >= 2019:
    print(0)
    exit()
else:
    for i in range(L,R):
        for j in range(L+1,R+1):
            ans.append((i*j)%2019)
ans.sort()
print(ans[0])


### FIXED CODE ###

L,R = map(int,input().split())
ans = (L*(L+1))%2019
if R-L >= 2019:
    print(0)
    exit()
else:
    for i in range(L,R):
        for j in range(L+1,R+1):
            if ans > (i*j)%2019:
                ans = (i*j)%2019
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)
S = sum(A)
NUM = [0]
for j in range(1,100005):
    num_j = A.count(j)
    NUM.append(num_j)
for k in range(Q):
    S += (C[k]-B[k]) * (NUM[B[k]])
    NUM[C[k]] += NUM[B[k]]
    NUM[B[k]] = 0
    print(S)



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)
S = sum(A)
NUM = [0] * 100005
for a in A:
    NUM[a] += 1
for k in range(Q):
    S += (C[k]-B[k]) * (NUM[B[k]])
    NUM[C[k]] += NUM[B[k]]
    NUM[B[k]] = 0
    print(S)
### BUGGY CODE ###

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

while True:
    for i in range(2,min(a,b)+1):
        if a%i == 0 and b%i ==0:
            gcd *= i
            a = int(a/i)
            b = int(b/i)
            break
    else: break
print(gcd)
    
    

### FIXED CODE ###

def lcd(a,b): ##return least common multiple of a and b
    if a > b:
        return lcd(a-b,b)
    elif a < b:
        return lcd(b-a,a)
    elif a == b:
        return a

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